Maximum Entropy Heterogeneous-Agent Reinforcement Learning
Authors: Jiarong Liu
Yifan Zhong
Siyi Hu
Haobo Fu
QIANG FU
Xiaojun Chang
Yaodong Yang
Venue: ICLR 2024 spotlight (2024)
Keywords: cooperative multi-agent reinforcement learning
heterogeneous-agent soft actor-critic
maximum entropy heterogeneous-agent mirror learning
Primary area: reinforcement learning
TL;DR: A unified framework for learning stochastic policies in cooperative MARL.

Abstract: *Multi-agent reinforcement learning* (MARL) has been shown effective for cooperative games in recent years. However, existing state-of-the-art methods face challenges related to sample complexity, training instability, and the risk of converging to a suboptimal Nash Equilibrium. In this paper, we propose a unified framework for learning \emph{stochastic} policies to resolve these issues. We embed cooperative MARL problems into probabilistic graphical models, from which we derive the maximum entropy (MaxEnt) objective for MARL. Based on the MaxEnt framework, we propose *Heterogeneous-Agent Soft Actor-Critic* (HASAC) algorithm. Theoretically, we prove the monotonic improvement and convergence to *quantal response equilibrium* (QRE) properties of HASAC. Furthermore, we generalize a unified template for MaxEnt algorithmic design named *Maximum Entropy Heterogeneous-Agent Mirror Learning* (MEHAML), which provides any induced method with the same guarantees as HASAC. We evaluate HASAC on six benchmarks: Bi-DexHands, Multi-Agent MuJoCo, StarCraft Multi-Agent Challenge, Google Research Football, Multi-Agent Particle Environment, and Light Aircraft Game. Results show that HASAC consistently outperforms strong baselines, exhibiting better sample efficiency, robustness, and sufficient exploration.

Published as a conference paper at ICLR 2024
MAXIMUM ENTROPY HETEROGENEOUS-AGENE REINFORCEMENT LEARNING
Jiarong Liu Yifan Zhong?.2, Siyi Hu",
Haobo Fu', Qiang Fu', Xiaojun Chang", Yaodong Yang Institute for AI, Peking University, National Key Laboratory of General AI, BIGAI, 3 University of Technology Sydney, "Tencent AI Lab
ABSTRACT
Multi-agent reinforcement learning (MARL) has been shown effective for coop- erative games in recent years. However, existing state-of-the-art methods face challenges related to sample complexity, training instability, and the risk of con- verging to a suboptimal Nash Equilibrium. In this paper, we propose a unified framework for learning stochastic policies to resolve these issues. We embed cooperative MARI problems into probabilistic graphical models, from which we derive the maximum entropy (MaxEnt) objective for MARL. Based on the MaxEnt framework, propose Heterogeneous--Agen Soft Actor-Critk (HASAC) algorithm. Theoretically, we prove the monotonic improvement and convergence quantal response equilibrium (QRE) properties of HASAC. Furthermore, we generalize a unified template for MaxEnt algorithmic design named Maximum Entropy Heteeoogeneoss-Aern Mirror Learning (MEHAML), which provides any induced method with the same guarantees as HASAC. We evaluate HASAC on six benchmarks: Bi-DexHands, Multi-Agent MuJoCo. StarCraft Multi-Agent Chal- lenge, Google Research Football, Multi-Agent Particle Environment, and Light Aireraft Game. Results show that HASAC consistently outperforms strong base- lines, exhibiting better sample efficiency, robustness, and sufficient exploration.
INTRODUCTION
Cooperative multi-agent reinforcement learning (MARL) is a complex problem characterized by the difficulty of coordinating individual agent policy improvements to enhance overall performance of the entire team. As a result, traditional independent learning methods in MARL often lead to poor convergence properties (30; 3). To alleviate these difficulties, the centralized training decentralized execution (CTDE) paradigm (5; 19) assumes that global states and teammates' actions and policies are accessible during the training phase. This approach leads to the development of competent multi-agent policy gradient algorithms (40; 37; 38; 43; 42) well as value decomposition algorithms (27; 24; 41; 26; 33). Furthermore, eeterogeneous-agenn mirror learning (HAML) (15) provides a template for rigorous algorithmic design, which guarantees any induced algorithm of monotonic improvement of joint objective and convergence to Nash equilibrium (NE) (22).
Despite the thcoretical soundness of the HAML framework, HAML-derived algorithms suffer from two main challenges. First, these methods face challenges attributed to either sample complexity or training instability. On-policy algorithms, including HAPPO and HATRPO (13), require new sample data for each gradient step, which becomes very expensive as task complexity and agent numbers increase. Off-policy algorithms, on the other hand, observe training instability and hyperparameter sensitivity (45). Moreover, HAML-derived algorithms suffer from insufficient exploration, which can lead to suboptimal NE convergence. This is primarily due to the standard MARL objective they maximize, where there always exists a deterministic convergence solution (15; 28) and stochasticity is not inherently encouraged. Since the presence of multiple NEs is frequently observed phenomenon in many multi-agent games, these methods can fail to explore sufficiently and prematurely converge to a suboptimal NE, as we will show in Scction 3.2.
A possible solution to these challenges is to let agents learn stochastic behaviors in sample-efficient way. Similar to the case of single-agent RL (7), in cooperative MARL problems, stochastic policies enable effective exploration of the reward landscape, mastery of multiple ways of performing the
"Fqual contrihution. #oor done during internship Institute for AI, Peking University. 'Corresponding to <yandong. - yang@pku edu. end. See our page at https: / / tes. google e. com/vi ew / mehaar.

---

Published as a conference paper at ICLR 2024
task, and robustness when facing prediction errors (46). Unfortunately, while number of methods have achieved great success in iinle-agent RL settings (46; 7: 9; 17), solving such stochastic policy learning problems in cooperative MARL is challenging. Existing CTDE methods offer no convergence guarantee for learning stochastic policies in general cases. Recently, FOP (44) applies maximum entropy framework to multi-agent settings via value decomposition. However, FOP only provides convergence to the global optimum when a task satisfies the Siaiiidal--oool-Opppppe (IGO) assumption, which limits its applicability in general cooperative MARL problems.
In this paper, we propose the first theoretically-justin policies in cooperative MARL. Firstly, we model cooperative MARL as a probabilistic graphical inference problem (Figure 2), where stochastic policies arise as optimal solutions. Performing variational inference in this model leads us to derive the maximum entropy (MaxEnt) MARI. objective. To maximize this objective, we introduce heterogenenus ensures the properties of monotonic improvement and convergence to quantal response equilibrium (QRE), which is the solution concept corresponding to stochastic policies in game theory (20; 6). The key insight behind this theory is the joint soft policy decomposition proposition. Based on HASPI, we derive the setprrggeeouu-agenn soft actor-critic (HASAC) algorithm. Furthermore, generalize the HASPI procedure to the Maximum Entropy Heterogeneouss- Agent Mirror Learning (MEHAML) template, which offers a unified solution MaxEnt MARL problems and provides the same theoretical guarantees for any induced methods as HASAC. We test HASAC on six benchmarks: Multi-Agent MuJoCo (MAMuJoCo) (4), Bi-DexHands (2). StarCraft Multi-Agent Challenge (SMAC) (25), Google Research Football (GRF) (16), Multi-Agent Particle Environment (MPE) (19), and Light Aircraft Game (LAG) (23). Across the majority of benchmark tasks, HASAC consistently outperforms strong baselines, exhibiting the advantages of stochastic policies, namely improved robustness, higher sample efficiency, and sufficient exploration.
actor-critic framework for learning stochastic
soft policy tteration (HASPI) which
2 RELATED WORK
Multi-agent policy gradient (MAPG) methods have been shown effective for multi-agent cooperation tasks (5; 19). Yu et al. (42) discovers the effectiveness of PPO in multi-agent scenarios and introduces MAPPO. It inspires CoPPO (39), which preserves monotonic improvement property with a simul- taneous update scheme, HAPPO HATRPO (13), which proves monotonic improvement and NE convergence property with a sequential update scheme, and A2PO (34), which preserves per-agent monotonic improvement property. Guarantees of HAPPO HATRPO are enhanced by HAML (15), which abstracts a general theoretical framework and leads to several practical algorithms. While these methods are effective on challenging benchmarks, we show in Section 3.2 that due the standard objective they optimize. they tend to converge rapidly to a suboptimal NE when in proximity to it. Notably, the idea of NE can be considered as a notion of local optimum in cooperative MARL settings, and has been studied in many prior works (29; 36; 13; 15). To alleviate suboptimal NE convergence problem, we propose to learn stochastic policies, which maximize the MaxEnt MARL objective that we derive from probabilistic graphical models. We adopt QRE (20; 6; 11) as the solution concept in MaxEnt MARL framework, which generalizes NE when payoffs are perturbed by additional noise.
MaxFntt algorithms have achieved great success in single-agent RI. SQL (7) and SAC (8) learn optimal MaxEnt policies through soft Q-iteration and soft policy iteration respectively. They refresh SOTA performance, showcasing the robustness and effective exploration of stochastic policy. Levine (17) reviews these algorithms from a control as inference perspective. Unfortumately. learning MaxEnt policies with theoretical guarantees remains challenge in cooperative MARL settings. MASQL (36) adopts a multi-agent actor-critic architecture similar to MADDPG (19), extending SQL to multi-agent settings without providing any theoretical guarantees. FOP (44), on the other hand, is a decomposed actor-critic method (4; 35), which utilizes the decomposed critic instead of the centralized critic to learn individual policies. It factorizes the optimal joint policy of MaxEnt MARL under the IGO assumption (see Appendix A.2 for details), which leads to poor performance in complex scenarios. To overcome the constraint of IGO, MACPF (32) learns optimal joint policy during training phase and distills independent policies from the optimal joint policy to fulfill decentralized execution. Such a procedure can be considered as offline imitating learning, where independent policies strive to mimic the behaviors produced by the optimal joint policy, but they still lack the guarantee of converging to the optimum. In contrast, our approach is the first MaxEnt actor-critic method with theoretical guarantee, presenting an improvement to HAML-based algorithms. We augment the objective with entropy, propose HASPI, prove its monotonic improvement and QRE (20; 6; 11) convergence property without restrictive assumption, derive HASAC, and establish MEHAMI. template.
2

---

Published as a conference paper at ICLR 2024
3 PRELIMINARIES
3.1 COOPERATIVE MULTI- REINFORCEMENT LEARNING
We consider a cooperative Markov game (18) formulated by a tuple (N, (WS,A,r P,y,, d). Here, denotes the set of n agents, S is the finite state space, A II=_1_'' is the joint
N == (1,...... .l.....n]] action space, where A' denotes the finite action space of agent r: A + is the joint reward function, P: S x A x S + [0. 1] is the transition probability function, 7 E [), is the discount factor, and d E P(X) (where P(X) denotes the set of probability distributions over a set X is initial state distribution. In this work, X and (y)(n) to denote the set of permutations of integers { [i...., n.. known as the symmetric group. At time step & E ..)..., each agent E N is at state s, E S and then takes independent actions at T' (e)ss) where x² is the policy of agent Let a, (a!.....af) aF) E A denotes the joint action and π (-1s)) = II,-= x² (+'|s) denotes the joint policy. We denote the policy space of agent i as IIo A {XXEST' (+1|s) IV' E S]. and the joint policy space II (II' ,...., II").. The agents receive joint reward r (st, ar) and move to the next state St+1 ~ (. az). The initial state distribution d, the joint policy and the transition kernel P induce marginal state distribution at
the notation P(X) to denote the power set of a set
time t, denoted by p't We define the (unnormalized) marginal state distribution Pn - > P'.. The standard joint objective of all agents is to maximize the expected total reward, defined as
T
[T) Eageroppe right aisT
(St, at)
(1)
3.2 LIMITATIONS OF EXISTING COOPERATIVE MARI METHODS
Existing MAPG methods maximizing the standard joint objective (Equation 1), such as MAPPO and НАРРО, may fail to find the optimal NE and converge prematurely. We analyze this problem by considering a singe-state 2-agent cooperative matrix game as shown in Figure
Agent
Agent
Agent
A
Agent 2
-20
-20
Agent
A
0,36
0.12
0.12
Agent
B
-20
-20
0.12
0.04
0.04
C
-20
-20
20
0.12
0.04
0.04
(a) Reward matrix
(b) Initial joint policy
(c) Final joint policy π
Figure 1: A single-state 2-agent cooperative matrix game. (a) is the reward matrix of joint actions. (b) represents the initial joint policy и formed by both agents taking the individual policy = {0.6, 0.,, 0.2). (c) represents the final joint policy π that MAPPO and HAPPO converge to, deterministically choosing action (A, A).
Agents each choose from three possible actions {A, B, and receive a joint reward. In this case, AA, (B, B). (C, C) are three different NEs with rewards of 5, 10, 20, with (C, being the optimal NE. To simulate common scenarios where finding the global optima is challenging and, due to the learning
the early stages, agents are updated towards some reasonably good local optima initially, we consider setting where agents assign a higher probability to action (A, A). as shown in Figure 1b. By exact calculation (see Appendix B), we find traditional algorithms like MAPPO and HAPPO converge rapidly towards the suboptimal point (A, A), failing to identify the Pareto-optimal equilibria (C, C"), as shown in Figure Ic, which is also corroborated by our experiment (Section 5.
The explanation is that maximizing the standard joint objective (Equation 1) leads to convergence towards the deterministic policies exploiting the local optimum they have explored so far (28). Specifically, the standard objective discourages any unilateral deviation from the local optimum it will result in a decrease in the joint reward. As a result, agents tend to deterministically converge to the suboptimal NE. To address this issue, propose to learn stochastic behaviors, which always preserve the probability of selecting currently underexplored actions, and will eventually converge to the QRE where action probability is proportional to the exponential of action value. We will show in the experimental section that our method could successfully converge to the Pareto-optimal equilibrium (C, C), even when it has a higher probability of choosing action (A, A) initially.
Wee write a², a, and when we refer the action, joint action, and state to values, and a², and to random variable.
3

---

Published as a conference paper at ICLR 2024
4 METHOD
In this section, we establish maximum entropy heterngeneous-agen reinforcement learning a framework for learning stochastic policies in cooperative MARL settings, which alleviates the suboptimal convergence problem mentioned in Section 3.2. We name it heterogeneons-ageen (HA) it is substantial improvement to HARL (45), its Proposition builds upon the prior advantage decomposition lemma (13), and it is generally applicable to HA settings. This framework encompasses three key components, including the derivation of MaxEnt MARL objective from a probabilistic inference perspective in Section 4.1, the HASPI procedure and HASAC algorithm in Section 4.2, and the unified MEHAMI. template for theoretically algorithmic design in Section 4.3.
4.1 MAXIMUM ENTROPY MULTI-AGENT REINFORCEMENT LEARNING
To formalize the idea of learning stochastic policies (-Is:), we embed cooperative MARL problem into the PGM (Figure 2). Following Levine (17), introduce an additional optimality variable Or, which takes on bi- nary values indicating the optimality of joint actions taken by all agents. Specifically, O = denotes that time step is optimal, and model it p( O; =|/se, a.) x exp(r(s;, (s, ae)). Then use structured variational infer- ence to approximate the posterior distribution p(r =
O
O2
O
a
a
a
1) x p(s:) I p( |Sc, ae)
exp E T(s.. ai)
82
trajectory т with the distribution (())
(St++1 ((s ( /se, a [a)(())s)), where we fix the envi-
Figure 2: The probabilistic graphical model for cooperative MARL.
romment dynamics (s2)) p(s1) and ((s++1 1st ax)
p(St+1/ss |S,, a,) to avoid risk-seeking behaviors (17). This
inference procedure leads to the maximum entropy (MaxEnt) objective of MARL (see Appendix C):
r (st, + Σ E (f1ss)
J(T) = Bap a BITT
(2)
where a is the temperature constant that trades off between reward and entropy maximization, and when a 0, the objective is reduced to standard MARL.
Augmenting standard MARL objective with an entropy term (Equation 2) aligns with the solution concept of quantal response equilibrium (QRE) proposed by McKelvey & Palfrey (20), which is generalization of the standard notion of Nash equilibrium (NE) in game theory. In a QRE, payoff's are perturbed by additive disturbances (entropy term our case) so that players do not deterministically choose the strategy with the highest observed payoff, but rather assign the probability mass in its strategies according to every strategy's payoff (6). The following Theorem shows that the QRE policies of MaxEnt objective
be represented Boltzmann distributions:
Theorem (Representation of QRE). joint policy क TORE E increase the maximum entropy objective (Equation 2) by unilaterally altering its policy, i.e.,
QRE if none of the agents can
V. E IT',J ( I J (TTRR))
Then the QRE policies given by
exp (a (a=",, inm one [0mgms (s, a' aa))
Vi N where the soft Q-functions defined follows,
(a'ls)
(3)
Evea exp
a aa-1E inm gas [Q (s, a a-1)]
Σ o ((( + (1ss))
an( (s, +
8u
an
(4)
Proof can be found in Appendix D. Theorem illustrates the connection between QRE policies and an energy-based model, where the term Q ToRes (8, a)) serves as the negative energy. When a >
4

---

Published as a conference paper at ICLR 2024
the QRE policies (Equation 3) are longer deterministic but rather can represent all the ways of performing a task. This suggests that the inclusion of entropy term makes the policy TQRE stochastic, enabling more effective exploration of the environment (21), which is consistent with our initial goal of learning stochastic policies in MARI. settings.
4.2 HETEROGENEOUS AGENT SOFT ACTOR ACTOR-CRITIC
In this subsection, develop helerooenneous-geen soft policy iteration (HASPI) maximize MaxEnt objective (Equation 2), which alternates between joint soft policy evaluation and heterogeneous-agent soft policy improvement, and then derive HASAC based on this theory.
4.2.1 HETEROGENEOUS-AGENN SOFT POLICY ITERATION
In joint soft policy evaluation step of HASPI, we compute soft Q-value from any Q(s, a) SxA - IR by repeatedly applying soft Bellman backup operator r given by:
I' ((, a) - r(ss a) + +.BaspPPV (s'),
(5)
where ((s) = Ea ((s,a) + Σ H (f1s))
(#1ss)))
(6)
the soft value function. We can obtain the soft Q-function of any joint policy shown in Lemma 4.1. Notably, the same method for updating soft Q-function has been proposed in FOP (44) since it is the straightforward application of soft Bellman equation.
Lemma 4.1 (Joint Soft Policy Evaluation). Consider the soft Bellman backup operator I' and mapping Qo : 8 A + R with |A| < 0o, and define Qk+1 = I Qk. Then the sequence Qu will converge to the joint soft Q-fumction π as k + oc.
Proof can be found in E. In policy improvement step, show that the joint policy can be updated based on individual policy updates. To this end, we first introduce the following definition. Definition 1. Let 11:m = ff..-..,ke im S N be an ordered subset of agents, and let -issm refer to its complement. We write in when we refer to the htth agent in the ordered subset. Correspondingly, the multi-agent soft Q-function is defined as
Q
(s,at!i)) E,,
f1.m Frrm
Qn (s,a"1 (1mm)
) +a Σ H ((ss))))
(7)
iE iE-i1m
In the case where n. Q (s, atin)) takes the form Q a), representing the joint soft Q-function. When m = 0, i.e., 81:m = 0, the function represents the soft value function V (s).
With this notation defined, we introduce pivotal proposition that shows the joint soft policy update can be decomposed into a multiplication of sequential local policy updates.
Proposition (Joint Soft Policy Decomposition). Let π be a joint policy, and in:n E Sym(n) be an agen! permutation. Suppose that, for each state s and every m I,...:7,
exp [
Q (s, a amammmmm1. Am
miin TT
DKL.
7m (.5m(s)
f2mm
mani
11
(8)
f1:m-1
Mo (s, al1mm-1)
where a f11m-1 is drawn from the policy neww normalizes the distribution. Then the joint policy satisfies the following:
Aaom
(-1s) and the partition function Zra (8, a
exp ( 2.mms (8,
Tnew = arg min DELL wenl
π (-1s)
(9)
7T.
Proof can be found in E.2. Proposition 1 holds significance due to the crucial insight it provides, suggesting that a MaxEnt MARL problem can be considered as a sum of n MaxEnt RL problems. It indicates effective heterogeneous--nn agget approach to improving the joint soft policy in multi- agent learning, where each agent optimizes individual KL-divergence sequentially leading to the optimization of joint soft policy. To formally extend the above process into policy improvement procedure with theoretical guarantees of monotonic improvement and convergence to QRE, we propose the heterogeneous--gen soft policy improvement formalized below.
5

---

Published as a conference paper at ICLR 2024
Lemma 4.2 (Heterogeneous-Ageenl Soft Policy Improvement), Let
ii: Letiin permutation, and for every = =....,, let policy T'j II'm and x be the optimizer of the minimization problem defined in Equation 8. Then Q (8, a) 2 @ a) for all (8, a) E S A with AA| < and J (Tnww) 2 (Told)-
SSmm(n) be agent
Proof can be found in E.3. Lemma 4.2 guarantees that soft Q-function and MaxEnt objective monotonically increase at each policy improvement step. Next, we propose hetenogeneous-agenn soft policy iteration, which alternates between joint soft policy evaluation and hetcrogeneeou--ggett soft policy improvement, and prove that joint policy л converges
QRE.
Theorem 2 (Heterogeneous-AAee Agent Soft Policy Iteration). For any joint policy E II, if we repeatedly apply joint soft policy evaluation and heterogeneeuu--gent soft policy imprevement from II n² converges to TORE in Theorem 1.
II' Then the joint policy
Proof can be found in E.4. To obtain such theoretical results, the updating approach in Proposition 1 plays a pivotal role. Lemma 4.2 ensures that, through the updates in Proposition soft Q-function increases monotonically, leading to convergence of the policies. Eventually, none of the agents is motivated make update (Equation 8) convergence, thereby establishing QRE.
4.2.2 PRACTICAL ALGORITIIM
In practice, large continuous domains require us to derive practical approximation to the procedure above. We will use function approximators for both centralized soft Q-function Qe (st. ax) and tractable decentralized policies т gi (af""ss)) for each agent ém parameterized respectively by and dnmn, and alternate between optimizing both networks with stochastic gradient descent.
The centralized soft Q-function parameters can be trained minimize the Bellman residual
(Q( BL
(Qo (st, a.) ac) + +yB (Vg (8)=1))))²
where the soft value function implicitly parameterized through the soft Q-function parameters via Equation 6. Then we draw a permutation i1=m E Sym(n) and sequentially update the policy each agent im according to Equation 8. The policy parameters can be learned by directly minimizing the expected KL-divergence in Equation 8 disregarding the constant log oog-pariiionn function
Jein (6im = BaanDD 11mm1
f1om-1
fy Son glm
[e
log x Son (iim
(a." |ss|
Q modd :6 Nt:
a
11m
(10)
We refer to the above procedure HASAC and Appendix F for its full pseudocode.
4.3 MAXIMUM ENTROPY HETEROGENEOUS- MIRROR LEARNING
In addition to updating policies by directly minimizing the KL-divergence Equation 8, we aim to propose generalized HASPI procedure that provides range of solutions to MaxEnt MARL problem. To this end, we start by introducing the necessary definitions the operators proposed in HAML (15): the drift functional (HADF) D'r (#'|s, (1.m) which, intuitively, is notion of distance between T' and #', given that agents f1.m just updated qh. the neighborhood operator U4 (T') which forms region around the policy x"; as well as a sampling distribution 3r P (S) that continuous in π (see detailed definitions in Appendix A.3). As shown in (15; 14), these operators allow for effective abstraction of standard RL and MARL methods due to their generality.
We present the generalized HASPI using these operators. In heterogeneoou--geen soft policy improve- ment step, we redefine the operator that agents optimize as follows,
Definition Let N, 11am P(-i), and De be HADF of agent i. The maximum entropy heterogeneous- mirror operator (MEHAMO) integrates the soft Q-function as
(M Di mdmm
Vx
(s) 2 R51mm wi Qiime Aim a²)
log n' (d'1s) Dí (* (*'1s, 71m) (#)),
Then we propose MEHAML Algorithm template to formalize generalized heterogeneous--genn soft policy iteration. Notably, HAML. special instance of template when

---

Published as a conference paper at ICLR 2024
Algorithm 1: Maximum Entropy Heterogenneou--Agem Mirror Learning
Initialise joint policy To = (mo....,, :
for k = 0, 1.... do Compute the soft Q-function Q (s, a) for all state-(jointaattion pairs (s, a); Update Qx (s, a) according to the soft Bellman equation (Equation 5);
Joint Soft Policy Evaluation
Draw a permutaion 11:m of agents random:
for 1: n. do
M
(rlm) D
Make an update " *k+1
arg max
Bag
M
ViL (s)
Mim
Fm Et (11
(Generalized) Heterogeneons-Ageet Soft Policy Improvement
end end
Output: A limit-point joint policy Toc
Despite the presence of a drift penalty and neighborhood constraint. optimizing the MEHAMO sequentially sufficient to guarantee the same desired properties as HASPI. We establish the complete list of the core MEHAML properties in Theorem 3, which confirms that any method derived from Algorithm has the desired properties of monotonic improvement of the MaxEnt objective and QRE convergence (detailed proof can be found in Appendix G).
Theorem (The Core Theorem of MEHAML). Let no E IL, and the sequence of joint policies (Tw)k= be obtained by MEHAML algorithm I induced by D' _t'', Vi E N, and 3... Then, the joint policies induced by the algorithm enjoy the following list of properties (1) Attain the monotonic improvement property J (T&+1) 2 J (TT)). (2) Their value functions converge to a quantal response value function limg VAL VQRE (3) Their expected returns converge to a quantal response
return limg- J [TTR) JURE, (4) Their w-limit set consists of quantal response equilibria.
Proof sketch. We divide the proof into four steps. In Step 1, we show that the sequence of soft value function (V=,)keN increases monotonically and converges to limit point. In Step 2, we show the existence of limit points म of (T&) keN, and that they are fixed points of the MEHAML update. In the most important Step 3, we prove that is also a fixed point of soft policy iteration by leveraging the concavity of MEHAMO. Step 4 finalizes the proof, proving that fixed points of soft policy iteration are QRE policies.
By selecting appropriate HADFs and neighborhood operators that satisfy the definitions, Algo- rithm has the potential to generate various poorreicalll-jussifeee algorithms to solve MaxEnt MARL problem. The drifts D'x (+' [s, (5,m) can serve soft constraints, such as KL-divergence, controlling the distance between A' and N²' when the agents ji.m have just updated to q Ad- ditionally, the neighborhood operators UI2 can generate small policy-space subsets, serving as hard constraints, then the resultant policy improvement will remain within small range due to the fact that nt' E Ui= (T'). Vi E N, E II'. Therefore, algorithms equipped with appropriate HADFs and neighborhoods can learn stochastic policies in stable and coordinated manner. In summary, MEHAML provides a template for generating theoretically sound, stable, monotonically improving algorithms that enable agents to learn stochastic policies to solve multi-agent cooperation tasks.
EXPERIMENTS
To demonstrate the advantages of the stochastic policies learned by HASAC, we conduct compre- hensive experiments on the matrix game Section 3.2 and six benchmarks - MAMuJoCo (4), Bi-DexHands (2), SMAC (25). GRF (16), MPE (19), and LAG (23)². It is important to note that while HASAC is originally designed for continuous actions, we employ a Gumbel-Softman (10) to ensure that HASAC would work for discrete actions. Compared to existing SOTA MAPG methods, HASAC achieves the best performance in 31 out of 35 tasks across all benchmarks. In addition to final performance, experimental results (see full experimental details and hyperparameter in Appendix
PHASAC achieves best performance on fully cooperative MPF and LAG tasks. See Appendix H.2.5 and H.2.6 for full results.
7

---

Published as a conference paper at ICLR 2024
Harte Came
Shactall Purdersm
Pam1o
Matrix Game
Catch Abreast
(c) Two Catch Underarm
Lift Underarm
Mndter2die dv3
academyy coreer
3000
3000
1000
Dez (g) RPS (2 agents)
Dap
(e) 3:2-gee HalfCheetah
(f) 6x 1xx1xAAgee --ggent Walker2d
(h) Corner (ll agents)
Figure 3: Performance comparisons selected tasks of multiple benchmarks.
Map
Difficulty
HASAC
HAPPO
HATRPO
MAPPO
QMIX
FOP
Timesteps
8m__s vs_ 9m
Hard
97.5(1.2)
83.8(4.1)
92.5(3.7)
87.5(4.0)
92.2(1.0)
23.4((.6)
le7
5m vs_6m
Hard
90.0(3.9)
77.5(7.2)
75.0(6.5)
75.0(18.2)
77.3(3.)
46.9(5.3)
le7
3s5z
Hard
100.0(0.0)
97.5(1.2)
93.8(1.2)
96.9(0.7)
89.8(2.5)
93.0(0.8)
le7
10m. vs vs_1Im
Hard
95.0(3.1)
87.5(6.7)
98.8(0.6)
96,9(4.8)
95.3(2.2)
12.5(6.2)
lc7
MMM2
Super Hard
97.5(2.4)
88.8(2.0)
97.5(6.4)
93.8(4.7)
87.5(2.55
37.5(28.1)
207
3x52_ _s_ ________666 3662
Super Hard
82.5(4.1)
66.2(3.1)
72.5(14.7)
70.0(10:7)
87.5(12.6)
0.0(0.0)
267
corridor
Super Hard 90.0(10.8)
92.5(13.9)
88 882.(2
97.5(1.2)
82.8(4.))
0.0(0.0)
2e7
6h_vs_8z 8z
Super Hard 95.0(3.1)
76.2(3.1)
78.8(0.6)
85.0(2.0)
7,0(27.0)
0.0(0.0)
4e7
Table 1: Median evaluate winning rate and standard deviation on eight SMAC maps for different methods. All values within standard deviation of the maximum score
marked in bold.
H) show the following advantages of stochastic policies: (1) HASAC exhibits similar performance
across different random seeds and higher training stability (2) HASAC shows higher learning speed
compared to existing algorithms, and (3) HASAC improves agents' exploration, which facilitates policies escape from suboptimal equilibria and converge towards higher reward equilibrium.
5.1 EXPERIMENTAL RESULTS
Matrix Game. We show the results of HASAC, НАPPО, MAPPO over 200 learning episodes in matrix game (Figure la). HASAC escapes local optima and achieves the Pareto optimum due the leamedd stochastic policies, while the other two methods fall into the suboptimal NE (Figure 3a).
Bi-DexHands. Bi-DexHands offers numerous bimanual manipulation tasks that match various human skill levels. In the challenging Catch Abreast, Two Catch Underarm, and Lift Underarm tasks (Figure 3b, 3c, and 3d), all on-policy methods fail within 10m steps due to low sample efficiency. HATD3 (45), the other hand, exhibits very high variability and prematurely converges to local optima. In contrast, HASAC outperforms the other five methods by a large margin. It also exhibits higher convergence speed and improved robustness, demonstrating the benefits of stochastic policies.
Multi-Agent MuJoCo. We compare our method to HAPPO, MAPPO, and HATD3 in ten MAMu- JoCo tasks (see Appendix H.2.2). Figure 3e, 3f, and the other results in Appendix H.2.2 demonstrate that HASAC enjoys superior performance over the three rivals both in terms of reward values and learning speed. It's worth noting that, although both HATD3 and HASAC are off-policy algorithms, we generally observe that HASAC learns faster with higher sample efficiency compared to HATD3, This is because the exploration mechanism of HATD3 involves adding Gaussian noise to a determin- istic policy, resulting in lower exploration efficiency, requiring more samples to explore the reward landscape. In contrast, HASAC, due its inherent encouragement of exploration within stochastic policies, can effectively explore the entire reward landscape. thus learning better behaviors rapidly.
StarCraft Multi-Agent Challenge. We evaluate our method on four hard and four super-hard maps. As shown in Table I, HASAC achieves over 90% win rates in 7 out of 8 maps and outperforms other strong baselines in most maps. Notably, in particularly challenging tasks such as 5m_ 6m, 3s5z 3352. and 6h vs 8z, observe that HAPPO and HATRPO would converge towards suboptimal NE. In addition, FOP is unable to learn meaningful joint policy in super-hard tasks due to its reliance the IGO assumption. By contrast, HASAC consistently achieves superior performance
8

---

Published as a conference paper at ICLR 2024
Ant-2 4x2
Ant-22 4x2
Mal Gamp
7000
7000
3000
Eslosse Wetion
1000
3000
1000
1000
1000
-30
107
25
50
75
1000
125
150
375
202
(2) Stochastic vs. deterministic
Efflect different Ani 4x2
Eiffect different matrix game
Figure 4: Performance comparison between HASAC with different hyperparameters on Ant-v2 4x2 task and matrix game. (a) The comparison indicates that stochastic policy can lead to hetter equilibrium and stabilize
training. (b) & (c) HASAC converges to different QRE with different temperature parameter
Agent
Agent 1
Agent
Agent
R
A
B
ILI025
ILI
Agrat
Agont
Agost
HASAC:
HASAC: a
(c)
HASAC:
10
(d)
Figure 5: Different temperature a leads to convergence of different QRE.
and shows the ability to identify higher reward equilibria due its extensive exploration. We also observe that HASAC has better stability and higher learning speed across most maps.
Google Research Football. We compare HASAC with QMIX, MAPPO, and HAPPO. As shown in Figure 3g and 3h we generally observe that both MAPPO and HАPPO tend converge non-optimal NE on the two challenging tasks, while HASAC exhibits the ability to attain higher reward equilibrium by learning stochastic policies which effectively enhance exploration.
5.2 ABLATION STUDY
We investigate the benefits of stochastic policies learned by HASAC and empirically show how dif- ferent temperature a values affect the stochasticity of policies, leading to different QRE convergence. Stochasticity. HASAC learns stochastic policies through maximizing the MaxEnt objective (Equa- tion 2). We compare it deterministic variant which utilizes deterministic policies with fixed Gaussian exploration noise to maximize standard MARL objective. The results in Figure 4a show that HASAC achieves a higher reward equilibrium and demonstrates better stability compared the deterministic variant, which exhibits high variance across the different runs. These findings highlight the importance of learning stochastic policies, which can improve robustness, facilitate escape from suboptimal equilibria, and converge to higher reward equilibrium.
Analysis of temperature policies. As illustrated in Figure 4b (we report a in legend), 4c, and 5, when a is large, policies predominantly emphasize maximizing entropy, leading poor performance due to the failure to exploit the reward signal. Conversely, when a is small, MaxEnt objective almost degrades to standard objective, leading suboptimal equilibrium due to inadequate exploration. A proper a achieves trade-off' between exploration and exploitation, eventually resulting in better performance. To obtain appropriate a, implement both fixed and auto-tuned (see Appendix H.I for details) a in practice.
We further show the effect of temperature on the stochasticity of
CONCLUSION
In this paper, we propose maximum entropy heterogeneous--geen reinforcement learning (MEHARL) unified framework for learning stochastic policies in MARL. This franework comprises three key components, including the PGM derivation MaxEnt MARL, the HASAC algorithm with monotonic improvement and QRE convergence properties, and the unified MEHAML template that provides any induced MaxEnt method with the same theoretical guarantees as HASAC. To demonstrate the advantages of stochastic policies, we evaluate HASAC on both discrete and continuous control tasks, confirming its superior performance and improved robustness and exploration. For future work, aim explore appropriate drift functionals and neighborhood operators to design more principled MaxEnt MARL algorithms that can further enhance performance and stability in multi- agent cooperation tasks.

---

Published as a conference paper at ICLR 2024
Acknowledgements. This work is sponsored by National Natural Science Foundation of China (62376013) and Beijing Municipal Science & Technology Commission (231110007722015),
REFERENCES
[1] Lawrence M Ausubel and Raymond J Deneckere. A generalized theorem of the maximum. Economic Theory, 3(1):99-107, 1993.
[2] Yuanpei Chen, Tianhao Wu, Shengjie Wang, Xidong Feng, Jiechuang Jiang, Stephen Marcus McAleer, Yiran Geng, Hao Dong, Zongqing Lu, Song- Zhu, and Yaodong Yang. Towards human-level bimanual dexterous manipulation with reinforcement learning. 2022.
[3] Caroline Claus and Craig Boutilier. The dynamics of reinforcement learning in cooperative multiagent systems. AAAI/IAAI, 1998(746-752);2, 1998.
[4] Christian Schroeder de Witt, Bei Peng, Böhmer, and Shimon Whiteson. Deep multi-agent reinforcement learning for decentralized continuous cooperative control. arXiv preprint arXiv:2003.0677 19, 2020.
Kamienny, Philip Torr. Wendelin
[5] Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Proceedings of the AAAI conference artificial intelligence, volume 32, 2018.
[6] Jacob K Goeree, Charles A Holt, and Thomas R Palfrey. Stochastic game theory for social science: primer on quantal response equilibrium. In Handbook of Experimental Game Theory, pp. 8 47. Edward Elgar Publishing, 2020.
[7] Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. In International conference on machine learning, pp. 1352-1361. PMIR, 2017.
[8] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor, 2018
[9] Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, et al. Soft actor-critic algorithms and applications. arXiv preprint arXiv: 2018.
[10] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterizztion with gumbel-softmatt arXiv preprint arXiv: /6/ 140, 2016.
[11] TS Kozitsina, IV Kozitsin, and IS Menshikov. Quantal response equilibrium for the prisoner's dilemma game in markov strategies. Scientific reports, 12(1):4482, 2022.
[12] Jakub Grudzien Kuba, Muning Wen, Linghui Meng, Haifeng Zhang, David Mguni, Jun Wang, Yaodong Yang, et al. Settling the variance of multi-agent policy gradients. Advances Neural Information Processing Systems, 34: 13458-134770 2021.
[13] Jakub Grudzien Kuba, Ruiqing Chen, Muning Wen, Ying Wen, Fanglei Sun, Jun Wang, and Yaodong Yang. Trust region policy optimisation in multi-agent reinforcement learning, 2022.
[14] Jakub Grudzien Kuba, Christian Schroeder de Witt, and Jakob Foerster. Mirror learning: A unifying framework of policy optimisation, 2022.
[15] Jakub Grudzien Kuba, Xidong Feng. Shiyao Ding, Hao Dong. Jun Wang, and Yaodong Yang. Heterogeneous-agent mirror learning: A continuum of solutions to cooperative marl. arXiv preprint 2008 01682, 2022.
[16] Karol Kurach, Anton Raichuk, Piotr Staúczyk, Michal Zajac, Olivier Bachem, Lasse Espeholt, Carlos Riquelme, Damien Vincent, Marein Michalski, Olivier Bousquet, al. Google research football: A novel reinforcement learning environment. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 4501 45100 2020.
10

---

Published as a conference paper at ICLR 2024
[17] Sergey Levine. Reinforcement learning and control probabilistic inference: Tutorial and review, 2018.
[18] Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pp. 157-163. Elsevier, 1994.
[19] Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb. OpenAl Picter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed
environments. Advances in neural
information processing systems, 30, 2017.
[20] Richard D McKelvey and Thomas R Palfrey. Quantal response equilibria for normal form games. Games and economic behavior, (0(1):6-38, 1995.
[21] Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans. Bridging the gap between value and policy based reinforcement learning. Advances in neural information processing systems, 30, 2017.
[22] John Nash. Non Non-cooperative games. Annals of mathematics, pp. 286-295, 1951.
[23] Xiaoteng Ma QihanL.u, Yuhua Jiang. Light aircraft game: A lightweight, scalable, gym- wrapped aircraft competitive environment with bascline reinforcement learning algorithms. https: / github.
//tos///eoooeecccatttt...o 2022.
[24] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder de Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning, 2018.
[25] Mikayel Samvelyan, Tabish Rashid, Christian Schroeder De Witt, Gregory Farquhar, Nan- tas Nardelli, Tim GJ Rudner, Chia-Man Hung. Philip HS Torr, Jakob Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. arXiv preprint arXiv: petii/9924443.. 2019.
[26] Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning, 2019.
[27] Jianyu Su, Stephen Adams, and Peter A. Beling. Value-decoomposition multi-agent actor-critics, 2020.
[28] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018. URL http:://inccmpleeeeeeeee net/book/ che-book-2nd html.
[29] Brian Swenson, Ryan Murray, and Soummya Kar. On best-response dynamics in potential games. SIAM Journal on Control and Optimization, 56(4): 2767, 2018.
[30] Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. In Proceed- ings of the tenth international conference on machine learning, pp. 330-337, 1993.
[31] J Terry, Benjamin Black, Nathaniel Grammel, Mario Jayakumar, Ananth Hari, Ryan Sullivan, Luis Santos, Clemens Dieffendahl, Caroline Horsch, Rodrigo Vicent, et al. Pettingzoo: Gym for multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 34:15032-15043, 2021.
[32] Jiangxing Wang, Deheng Ye, and Zongqing Lu. More centralized training, still decentralized execution: Multi-agent conditional policy factorization, 2023.
[33] Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. Oplex: Duplex dueling multi-agent geeannning, 2021.
[34] Xihuai Wang. Zheng Tian, Ziyu Wan, Ying Wen, Jun Wang, and Weinan Zhang. Order matters: Agent-by-agent policy optimization. arXiv preprint arXiv:2302.06200. 2023.
[35] Yihan Wang, Beining Han, Tonghan Wang, Heng Dong, and Chongjie Zhang. (DOP): Off- policy multi-agent decomposed policy gradients. In International Conference on Learning Representations, 2021. URL https: httss///ppprvvieeeee ner/forum? d=
11

---

Published as a conference paper at ICLR 2024
[36] Ermo Wei, Drew Wicke, David Freelan, and Sean Luke. Multiagent soft q-learning. arXiv preprint 10X9:1180.00987,, 2018.
[37] Ying Wen, Yaodong Yang, Rui Luo, and Jun Wang. Modelling bounded rationality in multi- agent interactions by generalized recursive reasoning. arXiv preprint arXiv: 1901.09216. 2019.
[38] Ying Wen, Yaodong Yang, Rui Luo, Jun Wang, and Wei Pan. Probabilistic recursive reasoning for multi-agent reinforcement learning. arXiv preprint N.0iv/99010092000 2019.
[39] Zifan Wu, Chao Yu, Deheng Ye, Junge Zhang, Hankz Hankui Zhuo, et al. Coordinated proximal policy optimization. Advances in Neural Information Processing Systems, 34:26437-26448, 2021.
[40] Yaodong Yang. Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean field multi-agent reinforcement learning. In International conference on machine learning, pp. 5571-5580. PMLR, 2018.
[41] Yaodong Yang, Jianye Hao, Ben Liao, Kun Shao, Guangyong Chen, Wulong Liu, and Hongyao Tang. Qatten: A general framework for cooperative multiagent reinforcement learning, 2020.
[42] Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo in cooperative multi- agent games. Advances in Neural Information Processing Systems, 15:246111226622 2022.
[43] Haifeng Zhang, Weizhe Chen, Zeren Huang, Minne Li, Yaodong Yang, Weinan Zhang, and Jun Wang. Bi-level actor-critic for multi-agent coordination. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 7325-7332, 2020.
[44] Tianhao Zhang, Yueheng Li, Chen Wang. Guangming Xie, and Zongqing Lu. Fop: Factorizing optimal joint policy of maximum-entropy multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 12491-12500. PMLR, 2021.
[45] Yifan Zhong, Jakub Grudzien Kuba, Siyi Hu, Jiaming Ji, and Yaodong Yang. Heterogeneous- agent reinforcement learning, 2023.
[46] Brian D Ziebart. Modeling purposeful adaptive behavior with the principle of maximum causal entropy. Carnegie Mellon University, 2010.
12

---

Published as a conference paper at ICLR 2024
Appendix
Table of Contents
A Preliminaries
14
A.1 Table of Acronyms.
14
A.2 Individual Iodivilual-Global Opttimal
14
A.3 Definitions and Assumptions
15
Proofs of Useful Lemmas
B Exact Calculation of Matrix Game
18
C Derivation of MaxEnt MARI Objective
21
D Proofs of Representation of QRE
22
E Proofs Agterageneous-AAeet Soft Policy Iteration
24
Proof Joint Soft Policy Evaluation
24
E.2 Proof of Joint Soft Policy Decomposition
24
E.3 Proof of Heterogeneoous-Agent Soft Policy Improvement
25
E,4 Proof of Heterogeencous-Agett Soft Policy Iteration
26
F Pscudocode of HASAC
27
Proofs The Core Theorem of MEHAML
28
Experimental Details
34
H.l Automatically Adjusting Eanp............................
34
H.2 Experimental Setup and Additional Results
34
H.3 Hyper-parameter Settings for Experiments
37
Ablation Study on Sequential Updates
42
13

---

Published as a conference paper at ICLR 2024
A PRELIMINARIES
A.1 TABLE OF ACRONYMS
Table 2 lists the main acronyms used in this paper.
Table 2: The acronyms used in this paper.
Acronym
Meaning
A2PO
Agent-by-agent Policy Optimization
CoPPO
Coordinated Proximal Policy Optimization
CTDE
Centralized training decentralized execution
FOP
Factorizing Optimal Joint Policy
GRF
Google Research Football
HА
Heterogeneouu--ggent
HADF
Heterogeneous drift functional
HAML
Heterogeneouu-AAgen Mirror Learning
HAPPO
Heterogeneoous-Agem Proximal Policy Optimization
HARL
Heterogeneoou--Agent Reinforcement Learning
HASAC
Heterogeneoou--Agen Soft Actor-Critic
HASPI
Heterogeeneous-agentt soft policy iteration
HATD3
Heterogenecou--geen Twin Delayed Deep Deterministic Policy Gradient
HATRPO
Heterogeneoou--Agent Trust Region Policy Optimization
IGO
Individual-Global-Opiiine
LAG
Light Aireraft Game
MACPF
Multi-Agent Conditional Policy Factorization
MADDPG
Multi-Agent Deep Deterministic Policy Gradient
MAMuJoCo
Multi-Agent MuJoCo
MAPG
Multi-agent policy gradient
МАPPО
Multi-Agent Proximal Policy Optimization
MARL
Multi-agent reinforcement learning
MASQL
Multi-Agent Soft Q-Learning
MaxEnt
Maximum entropy
MEHAML
Maximum Entropy Heterogeneoous-Agen Mirror Learning
MEHAMO
Maximum Entropy Heterogeneouu--ggen Mirror Operator
MEHARL
Maximum Entropy Heterogemeous- Reinforcement Learning
MPR
Multi-Agent Particle Environment
NE
Nash equilibrium
PGM
Probabilistic Graphical Model
PPO
Proximal Policy Optimization
QRE
Quantal response equilibrium
RL
Reinforcement learning
RPS
Run pass and shoot with keeper
SAC
Soft Actor-Critic
SMAC
StarCraft Multi-Agent Challenge
SQL
Soft Q-Learning
A.2 INDIIDDAA-GGLOBAA-OOOO
The Individual-Global--nne (IGO) assumption is introduced in (44) and can be stated below. Definition 3 (IGO). For optimal joint policy (a)s)) S x - [0, 1), if there exist individual optimal policies (a*)s)) A + [0, 1]] such that the following holds:
n. (als) = II (a*ss),
then, say that [xr] satisfy IGO for under
14

---

Published as a conference paper at ICLR 2024
The main limitation of IGO arises from the fact that during training, each agent's policy is updated based solely on its local Q-function, thereby ignoring the actions other agents. As discussed by Wang et al. (32), when multiple agents need to collaborate in decision-makinn they may fail to reach a consensus, updating their policies in the direction that increases their local Q-functions, but eventually resulting in decrease in the global Q-function.
A.3 DEFINITIONS AND ASSUMPTIONS
Throughout the proofs, we make the following regularity assumption introduced by Kuba et al. (13): Assumption 1. There exists E R. such that < 1 & 1, and for every agent i E N, the policy space IT is 1y-soft; that means that for every x6 E IT', 8 8, and at A', have x² (a' 2 n
In the following, we provide the essential definitions of the two key components, originally proposed by Kuba al. (15), that serve as the building blocks the MEHAMI. framework. Additionally, we present the definitions of soft advantage function and notion of distance that will be utilized in the proof Lemma A.2.
Definition 4. Let i NN, heterogeneeouuuegentt drift functional (HADF) D' of consists of a map. which is defined as
D' I x x {2i (-18, x 2tmm ::P(A)) - +RR,
such that for all arguments, under notation Dí (A'1s, +him) Di (#* (-1ss) |s, td)m)
1. D'r (# (1188 #1.m) 2 D'r (T (/mm) = (non-negativit)),
2. Dí (#'1s, ())m)) has all Gâteaux derivatives zero at A rtt (zero gradient),
We say that the HADF is positive if D'r (+' (f')))))) 0, vs S implies x n', and trivial if Vs for all π,, Thmm and #².
D1 (+' (5mm)
Definition 5. Let E N. We say that, Ui IIIII + + (IT') is a neighborhood operator if e II', Uh (x") contains closed ball, i.e., there exists a state-wise monotonically non non-deereasing metric x: II x1' + R. such that VIr E 11' there exists 8 > 0 such that x (  S 8 - #' E U (T²). Definition 6. Let i1:m {di,...,tml N and jı:k {J N be disjoint ordered subsets of agents, and let Q (8, (s, be the multi-agent soft Q-function. Then the multi-agent soft advantage function defined as
A (s, a 11ik a (Lim)) & Quieiiim (s 2ii a aamm) - Qua (s,.ai)))
(11)
Definition 7. Let X be a finite set and p X R, X - R be two maps. Then, the notion of distance between p and q that adopt is gîven by |p ql A maxxex lp(x) ((x)).
A.4 PROOFS USEFUL LEMMAS
Lemma A.I (Multi-Agent Advantage Decomposition). Let n be a joint policy, and i1,.... . fm be an arbitrary ordered subset of agents. Then, for any state and joint action a cm
A
(s, f1
A'd (s,a 1,05s)
(12)
1=1
Proof. (The lemma is proposed in (12) and we quote the proof from Kuba et al. (12)) By the definition of multi-agent soft advantage function,
AL m (s, a (1:m) 1)11.m mm (s, (mm)) (s)
Σ
e (s, aii))) - = -
(s.
A (s,a"ts-1,
which finishes the proof.
15

---

Published as a conference paper at ICLR 2024
The continuity of Qr is crucial requirement for proving Theorem later. Now we first prove that the inclusion an additional entropy term does not affect the continuity of Qr. which is the state-action value function in the single-agent setting, where denotes the policy of a single agent. And finally, we generalize the result to Qn in MARI..
Lemma A.2 (Continuity of Qx). Let π be policy. Then Qx(5, is continuous in
Proof. Let π and & be two policies. Then we have Q0 (8, a) a+(
((s,a) + Σ (s'(ss,))
Σ ((d'ss [(dd)))20(6:dd)))
v (a'ls') log (d'ls')
a() + (s
Σ P(s Σ ((
$ Σ P())(saa) Σ
+a D
t (a'ls') =
- logl))) (d|13))
= Σ P( a) - ((()ss)
+
(s')ss)
(T (a')s') - # (a' log * (a'ls') (log (a'ls') log (a'(('))))
5 P(d1s,0)) =d
+ [add's))) d)) #(d') (s
(d'ls') (1T (a'ls' - # (d'ls') (a'ls [dgg (logs (og log*((d(s)))
Σ ( Σ | - 1Q a')l + + Σ
#(a' 12x (( - (s(''aa))
o²
+ >< (d''ss))) - # (a'ls') [log π (d'ls') (a'ls') log (a'ls))))
5T (s) Σ || #| Qmax + Σ a 2
Σ (1|TT= #|| log log + + (a'ls') ) || llog log #1l)
"uuax |AA || #l + > 1|Q Q=11 + ary logmax क |A] || #|| + ary| log log +|
Hence, we get
||Q= Q+1 Qmaxx -| ||Q= +=1 logmax T.|A/ -| log log
16

---

Published as a conference paper at ICLR 2024
which implies
1| Q= - 7. mQuax + a log x) || - *|| + + log _ log #|
By continuity of π and log x, for any arbitrary e > 0, we can find 61 > 0 such that ||t - *| < 01
implies || +||
2x. 2l:lAlllQmmtttallon logass x) and 82 0 such that || #|l < 62 implies || log
(1-7)e
log +|| (2-T)e, Taking
min (8), when || #| 8 we get 1|Q Qall c, which
207
finishes the proof.
Corollary 1. From Lemma A.2 obtain that the following functions are continuous
(1) the state value function V*(s) E. (T(als)Qn(ssd) (als) log ((ass))
(2) the advantage function (s, = Q- (s),..
(3) and the expected total reward
(V)
Corollary 2 (Continuity in MARL). All the results about continuity in extend MARL. Policy can replaced with joint policy π.; as π is Lipschitz-continn contiiuuus in agent i 's policy n', the above continuity results extend to continuity in πe'. Thus, will quote them in our proofs for MARL.
17

---

Published as a conference paper at ICLR 2024
B EXACT CALCULATION OF MATRIX GAME
In this section, we provide an exact calculation of the matrix game in Scction 3.2. The initial policies of the matrix game represent the scenario where due to the exploration and learning in the early stages, agents may have explored a locally optimal solution (in this example action (A, A)) and assigned a high probability to it. The matrix game aims show that both MAPPO and HAPPO will converge towards this local optimum in expectation, while HASAC, owing to its optimization of the maximum entropy objective, has the potential escape this local optimum and converge towards superior solution.
We start by analyzing MAPPO. For both prrameter-sharinne and paa--aaattter-sirring versions of MAPPO, the policy is optimizing the following objective:
x (a*ls) F (a
arg max Egrapans TroTall
Ara (s, a) , 1,2
(13)
Note that we omit ratio-clipping in this tabular case, as this simpler and does not affect the final result. In this 2-agent single-state matrix game, 8 ~ Pmoi can be ignored as there is only one state. Value function Va (s) can be calculated exactly:
V was (s) Ennwss (Q (s, a)]
Bawn [r(s, a)]
0.36 5 + 0.04 10 0.04 20 4 (-20) + 2 0.04 (-20)
8.2
Similarly, the advantage function Am (s, a) can be calculated exactly as shown in Figure 6.
Agent
C
Agent 2
A
13.2
-118
-11.8
B
-11.8
18.2
-11.8
C
-11.8
-11.8
28.2
Figure 6: Advantage values Amay a8 for all joint actions in the first iteration.
Expanding objective 13, get
T = arg max (0.36 x 13.2 + x (-11.8) 2) X a(aa Als)
0.6
n²
+ (0.12 x (-11.8) + 0.04 x 18.2 0.04 x (-11.8)) x 7'aa' = B(s)
0.2
a'aa' Cls)
(0.12 (-11.8) 0.04 x (-11.8) + 0.04 (28.2))
0.2
= arg max max 3.2 x क (a' = Als) + (-5.8) x r'(a' = B|s) ) + 3.8) x a = C(s)
This will encourage स assign higher probability action A and lower probabilities action B and C. The updated policies will further encourage choosing action A in subsequent iterations. Finally, the policies will converge to the deterministic policies (1, 0, 0), 1,2.
For HAPPO, the agents update their policies sequentially. Without loss of generality, we assume they update the order of Agent and Agent Agent updates its policy according objective 13 and increases the probability of action A. Let new (pi, (P.,P2.P)) s.t. Pı > 0.6, < 0.2, Pa <
0.2, Ei Pj 1. Agent 2 updates its policy according the following objective:
18

---

Published as a conference paper at ICLR 2024
π ( () new (a+ls)
Tew new
arg max R Paa
(a (a/pp ATao (s, a)
Told [a (s)
arg max (0.6 PI x 13.2 0.6 pa x (-.1.) (-11.8) x 7² = Als)
+
x²
0.6
-0.2 P1 (-11.8) + 0.2 x P2 x 1 (-11.8) x T²(8² = B(s)
0.2
π 2 C|s)
+0.2 P1 (-11.8) + 0.2 (-11.8) 0.2 P3 x (28.2))
0.2
arg max (13.2 X1 11.8 X P2 11.8 x
(-11.8 x P1 + 18.2 11.8 p3) x (a² B(s)
(-11.8 11.8 p2 28. + P3 π
2 (a² Cls)
Since (13.2 x P1 11.8 P2 11.8 -5.8, (-11.8 x 100--1.881 action and lower probability to action B and C. Similar to MAPPO, the updated policies will further encourage choosing action in subsequent iterations. Finally, the policies converge to n' (1,0, 0). 1,2.
3.2, (-188 18.2 P2
Ps)
< -3.8, this will encourage assigning higher probability
By contrast, HASAC is possible to escape the local optimum and converge to better stochastic policies, we show below. Without loss of generality, assume the update order Agent 1 and Agent 2. We first consider the update of Agent 1, who optimizes the following objective:
T arg E. nart a a (8, (s, aa²) log π r'(a'ss)
x² arg max Bat adw [r(s, a²) a alog N (a ss]
Parametrizing x = -pt,P2,Ps!) Ps), we get
new
arg max n1
5pi - 14p2 - 12p3 opi log P1 ap2 log - ap3 log
s.t. P1 + P2 P3 =1
The solutions corresponding to different a are listed the left part of Table 3.
After the first update
Convergent (both)
C
P1
P2
P3
P1
P2
P3
0.9990
0.0001
0.0009
1.0000
0.0000
0.0000
0.9603
0.0107
0.0290
1.0000
0.0000
0.0000
5
0.7083
0.1171
0.1747
0.9849
0.0075
0.0076
10
0.5254
0.2136
0.2609
0.0221
0.0224
0.9555
1.5
0.4596
0.2522
0.2882
0.1278
0.1354
0.7368
20
0.4269
0.2722
0,3009
0.2514
0.2790
0.4697
Table 3: Exact calculation results for HASAC update. On the left we show the policy after the first update; on the right we show the policies of x!! and x² after convergence.
As a increases, the policy encouraged to be stochastic, trading off between stochasticity and reward maximization. With appropriate a, the policies will be able to assign higher probabilities to action B
19

---

Published as a conference paper at ICLR 2024
and C, thereby retaining the exploration of them. It then encourages exploration of action B and C' in subsequent updates. Finally, the convergent policies predominantly choose action C' while still being stochastic, shown in the right part of Table 3.
Thus, we show the benefit of stochastic policies and that in expectation, with appropriate a, HASAC is capable of escaping local optimum and converging to better stochastic policies. We note that the exact calculation results are generally consistent with the empirical results in Section 5.2 (this can be easily checked by computing the joint action probabilities and comparing with Table 5). An observation is that when a 5, theoretically it is not sufficient for escaping local optimum but empirically already results in learning the optimal actions (C, C). This may be due the fact that in practical implementation, HASAC learns centralized Q-function by sampling from the replay buffer, which introduces some randomness that causes slight deviations between the experimental results and the exact calculated ones.
20

---

Published as a conference paper at ICLR 2024
C DERIVATION OF MAXENT MARL OBJECTIVE
In this section, we derive the maximum entropy objective of MARL (Equation 2) by performing variational inference in Figure 2. In structured variational inference, our objective is approximate some distribution p(y) with another, usually simpler distribution q(y). In our case, we aim to approximate p(T), given by
T p(T) = p(si) II t=1
T Σ
p( ar) exp
r(se, at)
(14)
via the distribution
- q(s)) II t=1
g (a)g(())s)) = ((s)) II t=1
gss ax) II
9 (atm
(15)
where the joint policy ((ar/s)) follows fully independent factorization g( (se)
Im qin (at" (se) as we assume that agents are independent of each other under CTDE paradigm. To avoid risk-seeking behavior, we fix the environment dynamics, i.c., ((s1) p(s1) and g(se+1 [St,, a.) p(s--1 (st, ar). In structured variational inference, approximate inference per- formed by optimizing the variational lower bound (also called the evidence lower bound). In our case, the evidence is that O; = Vt E {1...., and the posterior is conditioned on the initial state s1. The variational lower bound is given by
log (( = log
p(O 81:7, a
log /
( a1.7)
p(O SI.T a
ds day.T
( a1:7)
p( (Or., 81:7; a1.r)
log an
((1I.T, aIT)
E aur
[log P(O1.r S1:7 a1:r) log ($1:2, a1rr).
where the inequality the last line is obtained via Jensen's inequality. Substituting the definitions of p(r) and q(T) from Equations 14 and 15, and according to q(Se+1|st. a.) = p(se+ (Se; ax), the bound reduces to
]]
log (Oi.)) 2 an
Σ
r (Sc, ai)
Σ m=1
log rm (a, (a/mmss)) 1se)
(16)
Optimizing this lower bound with respect to the policy q(ar (s) corresponds exactly to the following maximum entropy objective:
]
((T) Expr
Σ
(St, ar)
Σ (M' (fs)))
where multiply temperature parameter to the entropy term assign relative importance to entropy and reward maximization (9).
21

---

Published as a conference paper at ICLR 2024
D PROOFS OF REPRESENTATION OF QRE
Theorem (Representation of QRE). A joint policy QRE E QRE if none of the agents can increase the maximum entropy objective (Equation 2) by unilaterally altering it policy, Le.,
ViEN, ETT ( S { (TTRE))
Then the QRE policies given by
exp (a (R, inm amr 1Qmmn (s. aaa",nn a ")])
ViE TORE aa where the soft Q-functions defined follows,
(3)
Eseese exp 11-1 mar 1Q mome (s, b¹, a [)]
an( = + -
Σ 72 (() + Σ H (x' (1si)) 80 =, a
(4)
Proof. First, we consider the following constrained policy optimization problem to agent i: for given state S,
max E a (Q - Σ
Σ a
log T² (alls) log T (alls),
s.t. Σ n² (a'ls) 11
11
a'EA'
We consider its associated Lagrangian function as follows,
L(T', A) Eainii in (0x - Σ Σ N (a'ls) (a'ls) + +1( Σ t' (a'ls) 1)
a'Ed'
II aEAj=1
" (a'ls) (x) a Σ
Σ
n³ (a) (a)ls) log (adls) + A(
Σ
(a'ls) -1).
5=1
EEA
a'EAt
Then we consider the derivative of L(Tt, () with respect to nL, we obtain
AC(Ti,
Σ
Il n
Qn a algo loloo'''''ss)) + X.
0 (a'1s)
a''EA-
Let ac(m(A) (
= O, we know the optimal policy o satisfies the following condition,
नं (d'1s) = exp(a - "Ea-ea-- 1Qm (s,a', ") exp X 1).
Furthermore, since Eaiedi TH (a'ls) = we know optimal lagrange multiplier X satisfies
exp(1 2n = Σ
X
exp(a "Ra- [Qx (s, a², ")]),
A'EAt
i.e.,
X --=11 1- (1-10 Σ exp(a EE [Qm (s, a² a -1)1 a.
1
e'E.A
Finally, we obtain the optimal policy as follows,
expla 'E, in 1Qr (s, as, a
मं. (a'1s) EvEE exp(a Sappa--EA-inae EEg-aa-- (2 (s, bi, a a-)))
22

---

Published as a conference paper at ICLR 2024
Hence, when each agent can not increase the maximum entropy objective by unilaterally changing its policy, policies take the following form,
vi N, FORE (a'1s) arg max E Baini' mwn [Q moRe (s, a)] (-1a)
T (a'ls) log T (a'ls)
aiEA:
exp(a - -a- al- QRE Qmaaa (s, 8, a))
オ (a'ls) EoEE: expla -B--inngee Qregnn (8, b¹, a a)))'
which finishes the proof.
23

---

Published as a conference paper at ICLR 2024
E PROOFS OF HETEROGENEOOS--GEEN SOFT POLICY ITERATION
In this section, we introduce heterogeneous-agen soft policy iteration and prove its properties of monotonic improvement and convergence the QRE policies.
E.1 PROOF JOINT SOFT POLICY EVALUATION
For joint soft policy evaluation, we will repeatedly apply soft Bellman operator T', to Q(s, a) until convergence, where:
( a) - r(s, a) + TEg (V (s')l
(17)
((s) Ba-n ((s,a) Σ H (T (*1s))
(18)
In this way, shown in lemma 4.1, we can get Qx for any joint policy π
Lemma 4.1 (Joint Soft Policy Evaluation). Consider the soft Bellman backup operator x and mapping Qo : S A + R with |A| <, co, and define Qk+1 Qk. Then the sequence Qj: will converge to the joint soft Q-function a as oc.
Proof. We define the reward with entropy term as T (s. a) é r(s, a) (aaa)BBBa -BSppP (Ei= H H( (+1))) We can then express the update rule as:
Q + rx + (Q(s'aa)) a')]
and apply the standard convergence results for policy evaluation (28).
E.2 PROOF JOINT SOFT POLICY DECOMPOSITION
After we get Qx (s, a),, we draw permutation 1mm. E Sym(n) and update each agent's policy Tt according to the following optimization proposition:
Proposition (Joint Soft Policy Decompasition). Let n be joint policy, and in E Sym(n) be an agent permutation. Suppose that, for each state and every m
1,...:
Quh (s, a aaamm-m,,,, fm
Jmm
EniH
DEL
Son x
(Am(())
exp
11m
f1om
7 (8, a a11mm-1))
(8)
where a 211mm1 is drawn from the policy Neew normalizes the distribution. Then the joint policy satisfies the following:
81om
(-1s and the partition function Zmau (8, a
exp (3 Qums (8.
Taen arg min DRL. π (-1s)
(9)
Zma (8)
Proof. First, It (m (-1s)) denote
1 LQuu (s, ahim-,,, fm Fidd
DKL
x (Am
||
exp
from
Tack
11mm
E
$1im-
mmss (s, (s,a am)m
a
Suppose that there exists a policy क * T noows such that Lima (F (-(())) < Limras Cooau(Tnnch (Teow (-1s)), we have
En-* (Qray (8, a)] + Σ H (7* (+1s)) > EanTar mie 1Qra a)) + Σ
H (m (f1ss) (19)
1=1
From Equation 8, we have L Im Til
(irio (-1s))
im (m (-Is) for every m 1,... n, i.e. Fill
[Qu (s, a mimm- a - a log Tim (a'm [s)]
1
Tark
Mall
E
Q im (s, a ftm a,a'm) log 'm (a im [s)]
from
Morn wit
24

---

Published as a conference paper at ICLR 2024
Subtracting both sides of the incquality by IE farm
Q f1mm1 (5, aftmm-)) gives
mer
E i Tazk
(s, a ftom 1, a, - a log fm (a'm|s)
Mack
(20)
2 11im
A (s, aftim- ,, - a log म im (s)m
Combining this with Lemma A. gives
Amas (s, + Σ H (Thew (415))
Ea-
Σ
E
(Atr (s,, aftmm- atm)
log T (atm [s]]
Fimm
aatm mott
by Inequality 20
E
[Amm (s,, aitmm-1 ( a loo n' (afm mall
fimm
mar
aaton
==
Amau (), + E H (#' (-11))
Eant
The resulting inequality can be equivalently rewritten as
" Eara [Qma (s, a)] Σ H (#' (+1ss) EarTo. 10 (s, + a Σ H (T (*|s)), (21)
which contradicts Equation 19. Hence, for all π E II, Limal nnew (-1s)) S Limas (T(-) i.e.
exp (1Q 1mass was (8.
π new = arg min DKL # #EII
π (+|s)
Zmao (s)
which finishes the proof.
E.3 PROOF OF HETEROGENEOOS--GENT SOFT POLICY IMPROVEMENT
Then the soft Q-function and joint maximum entropy objective (Equation 2) has monotonic improve- ment property as formalized below.
Lemma 4.2 (Heterogeneoou--Aget Soft Policy Improvement). Let iisa Sym(n) an agent oid II'm and vm be the optimizer of the minimization problem defined in Equation 8, Then Q (s, a) 2 Qrau (3, a) for all (s, a) E S A
permutation, and for every m I....., n, let policy π im
with A| < oc and (Tnew) 2 J (Tll.)
Proof. From Proposition have
π (-1s) exp ( mey (s,
Nnew arg min DRT. WEll
arg min Lmm (+(s)))) well
ZT (8)
must be the case that Limas (Tnew (-1s)) < Limas (-s)) Hence
Eawaar 1mmae (s, a)] + a Σ H. (I (-91s) 2 Earnus (mma (s, a)] + a Σ (Táha (-1ss) = Vinaa (s).
1=1
(22)
25

---

Published as a conference paper at ICLR 2024
Last, considering the soft Bellman equation, the following holds: Qua (8, a) = r(s, a) ~ Fu
(s')]
S r(s, a) + T Bantee (Q [a) + Σ H (T (#16)) (by Inequality 22)
Sm (8,
(23)
where we have repeatedly expanded Q on the RHS by applying the soft Bellman equation and the bound in Inequality 22. Convergence to @eew follows from Lemma 4.1.
We use it to prove the claim as follows,
V VaRAn
E Bawwesn [Q (s) + H. (Teew (.'1s)
11
E Bawner (Q (s, + a Σ (nrew (-)s))((by Inequality 23)
2 Bawnas 12ras (s, a)] a
_ H (Tona (eIss) Inequality 22)
(s).
Subsequently, the monotonic improvement property of the joint maximum entropy return follows naturally, as
J (Tenw) Egnd (Vr (s) Bgnd (Vr,a (s)] J (Tau)) )
E.4 PROOF OF HETEROGENEOUS--GGEE SOFT POLICY ITERATION
The full heterogeneous- soft policy iteration algorithm alternates between the joint soft policy evaluation and the heterogeneeou--gent soft policy improvement steps, and it will provably converge to the QRE policies.
Theorem 2 (Heterogeneous-Agen) Soft Policy Iteration). For any joint policy E II, if we repeatedly apply joint soft policy evaluation and heterogeneous-agent soft policy improvement from n' II. Then the joint policy π II x² converges to TORE in Theorem 1.
Proof. Let Thk be the joint policy at iteration k.
First, by Lemma 4.2, have that QRa (s) bounded by Qmax for all æ E II (both reward and entropy are bounded). Hence, the sequence converges some limit point म.
a) I Q (s, a), and that the soft Q-function is upper-
Then, considering this limit point joint policy म. must be the case that Vi EW Vo E II' (T (TT
And we have
# (-1s) = arg max Exiuy [Q (s, a²) - a log (a/ls)
(1))))P()))
arg max Eawnn (+(1)))))()))
1Q*(s. (Q
(24)
Σ
Σ
n (a')x) log (a)l)),
1= EA
Last, following the proof of Theorem we have
exp (a (a''E, EE iani [Q (s,a",a a a)))
#ं (a'ls)
EvEA exp (a E--IEB-ia -i [Q (s, bi a ")])
Thus, a quantal response equilibrium, which finishes the proof.
26

---

Published as a conference paper at ICLR 2024
F PSEUDOCODE OF HASAC
Algorithm 2: Heterogeneous-Agent Soft Actor-Critic
Input:
temperature a, Polyak coefficient т, batch size B, number of: agents n, episodes K, steps per episode T, mini-epochs e; Initialize: the critic networks: Φi and Φ2 and policy networks: {0'), SEN replay buffer B, Set target parameters equal to main parameters Otarg. + Φ1, Prarg. f 02:
for .,., K 1 do
Observe state of and select action af To(-lo));
Execute at in the environment;
Observe next state Ot+1, reward rri
Push transitions (of, af; o(41: 1z). Vi E N, E 3) into B;
Sample random minibatch of transitions from B;
Compute the critic targets
min Quen.. (5411,2+1) - a Σ log Tà (si+1104zz) 11,2
= r+Y
a++1 ~ wo (-18441)
Update Q-functions by one step of gradient descent using
6 = arg min -
Σ (we - QΦ. (st, az)) for = 1, 2;
B
Draw a permutation of agents iiw at random; for agent im i1, -1,...,. in do Update agent im by solving
A'm arg
Fim
B
Σ
min Qø: 1=1.2
St,
11im-1 O2
1)
fm a
Bmm
(o,T*)
Jm 11m
0
mm
(o
fm 1an
im aog
im a0
lof
dim
where (ot) is sample from +T((-10)) which is differentiable wrt 0 via the reparametrization trick; with mini-epochs of policy gradient ascent; end
Update the target critic network smoothly
Orarg à porarg (1 p)p. for i 1,2; 2;
end
Discard Φ. Deploy (0r) iee in execution;
27

---

Published as a conference paper at ICLR 2024
G PROOFS OF THE CORE THEOREM OF MEHAML
First, we show that enhancing the MEHAMO (Definition 2) alone is sufficient to guarantee policy improvement, as demonstrated by the following lemma.
Lemma G.1. Let Vold and new be joint policies and let i1: E Sym(n) an agent permutation. Suppose that, for every state E S and every m 1,...,,, n,
M
( Dio
Vanas
(s)
M
Vauu (s)
(25)
Dim 4.m-
Then, Tnew is jointly better than Vold, so that for every state 8,
Vi (8) 2 Vasu (+).
Subsequently, the monotonic improvement property of the joint return follows naturally, as (Teww) =
Ennd [V
(5)] 2 Eandt [Vrue (s)] = J (TTmN)
Proof. By Inequality 25, we have
Q (s, 22mmmm 1amm-1,a"00 a."m) - a log New (a. [s)]
11mm
im Rall
T Sm
new
(,, T
new
ktim-1
(Qitim (s, a altim-1,
-a log uill (a*m [s)] ,a'm) (2imm),a''m)
fr n mottan
11:m
aati wust
D tm mall
frim 88 new
Tald
Subtracting both sides of the inequality by IF
Q
"ss, aftmm- gives
fimm $1:m-1
E 11:m 1 Waas
F1:m
.a
[A'm (s, a 41:m-1
aatmm
log mim (a [s)]
fm D
f1im now
(26)
E 'tom -1 mart
am mas (s, ft:m-1 ,a(m) - a log Told (a [s)]
Lati was
D fm Mou
Ae Told 18,
Let D may
(Tnew (s) A Σn=
TThew
18, F3im
Combining this with Lemma A.1 gives
m==
Amas (8, + Σ Hl nwwww (-91)))
D
(Tnew |s)
EF
22 21
$1:m
[A'm (s, a aimm- a²m) log fm (a [s)]
m=1
Dim i' Mail
f1:m- 18, 3T new
by Incquality 20
E
AA'mn (8, a from 1, 1,a'm) - a log Tim (a*m
moree am mest kom
m=1
- D km
Eny Told
(s, Tnew
(s:m-1)
Ana (s, a) + Σ H (Trda (+1s)) - Dran (Trota (s).
Egnma
i=1
28

---

Published as a conference paper at ICLR 2024
The resulting inequality can be equivalently rewritten
Ea-w (Qmas (s, a)] +
H (T (-11s) - mas (Trew 18)
1=1
(27)
7
Bawna (Tra (s, a)] + a
Σ
H (Todd (:11s) D Dinn (Tow (s) Vs S.
i=1
We use to prove the claim as follows,
yew (s) = Ea-wee 1 (8, a)] +
H (Thow (.11s)
Bawwee 10 a)) + a Σ H (nrow (-11s) D min (Tnew (8)
1=1
D was (Tnew [s) Banwter
10 (s, a) 1ueu (s, a)],
by Inequality 27
Ea-wa 14 (s, a)]
E (Told (.91s) Draa (Told (s)
+ D mau (Tnww (s) + Bawnhe 12 men (s, a) amuu (8, a)],
Visu (s) + mas nnw [s) + Earnun 1Q 1me. (s, Qmas [s)
Viua (s) + D mou [Tnow 1s) + Earman s/ouP (r(s, a) + 7, VVTan (s') - (d)-r(ss,)) m (s')
Visus (s) + mou nTww [s) + Baante s'mPP (Vreen (5') Vinas (s')
Vas (8) + y inf VV (s') - Viau (s')]
Hence VTT.. (s) Vin (s) 2 inf (Vaw (s') Vanu (s')].
Taking infimum over and simplifying
(1 11-7 --))ni inf [V (8) ViL.A (8) 2
Therefore, inf, [Vr... (s)- Vmaa (x) 2 0, which proves the lemma.
Then, any algorithm derived from Algorithm ensures that the resulting policies satisfy Condition 25, demonstrated by the following lemma.
Lemma G.2. Suppose agent im maximizes the expected MEHAMO
new
arg INXX
f10m-1
Vaaa
(8)
(28)
The Eldin (5((0)
Then, for every state s E S
(
(8)
M M Dim
Vauus
(s).
(29)
Dim
f1im-)
Hence, Thew attains the properties provided by Lemma G.I.
Proof. We will prove this statement by contradiction. Suppose that there exists so E S such that
( Di TTick
M
Vieas
(5o)
fr Viaus (so)-
Let us define the following policy tim.
= {f =
Jm
[mm [s) at 80
* bm ( (m))))
Told
n new
Am at + 8o
29

---

Published as a conference paper at ICLR 2024
Note that 4m is (weakly) closer to Told than nhw 8o, and at the same distance at other states.
Together with fim unu
fm ). this implies that 5' Uta (Told) ). Further,
M
B
Vmnas
(s)
Bma
Viria
(s)
Dim flim-1
Dim Tack
f1mm-
(Mm(tii Di T
= Smas (80)
11:ma-1
Varua
(50)
M
D Fi -Prn
f1:m
mal
(s0)
>
O.
The above contradicts The as being the argmax of Equality 28, A'm is strictly better. The contradiction finishes the proof.
Next, we prove the most fundamental theorem of MEHAML.
Theorem (The Core Theorem MEHAML). Let no E II, and the sequence of joint policies (TT))= be obtained by MEHAML algorithm I induced by D' _1,,, vi E N, and 3.. Then, the joint policies induced by the algorithm enjoy the following list of properties (1) Attain the monotonic improvement property J (T&+1) 2 J (TT)). (2) Their value functions converge to a quantal response value function limg- limg-150 V==== VQRE (3) Their expected returns converge to a quantal response
return limg- J (TTx) JORE, (4) Their w-limit consists of quantal response equilibria.
Proof. Proof of Property 1. follows from combining Lemma G.1 & G.2.
Proof of Properties 2, & 4.
Step convergence the value function. By Lemma G.I, we have that V (8) S VI (s), Vs E S, and that the value function is upper-bounded by Vmax- Hence, the sequence of value functions (Vrx) KEN converges. We denote its limit by V.
Step 2: characterisation of limit points. As the joint policy space IT is bounded, by Bolzano- Weierstrass theorem, we know that the sequence (TE))EN has convergent subsequence. Therefore.it has least one limit point policy. Let be such limit point. We introduce an auxiliary notation: for joint policy and permutation d1:m. let HU (T, fim) be joint policy obtained by MEHAML update from ı along the permutation 11:-
Claim: For any permutation 2im E Symm(n).
π = HU 21m)
Proof Claim. Let ने HU (#F, 2im) * π and (TK,))eN be a subsequence converging to ग. Let us recall that the limit value function unique and denoted as V. Writing Egp [ for the expectation operator under the stochastic process (ift.) KeN of update orders, for state E S, we have
0 = lim Egono
[V (8) V=x, (s)]
1-000
as every choice of permutation improves the value function
> lim P Ai = =im) (V - Via. [s)]
(mm) lim (Vin(( - ViTe (s)]
7-200
By the continuity of the expected MEHAMO (following from the continuity of the state-action value function (Lemma A.2), the entropy term, HADFs, neighbourhood operators, and the sampling distribution) we obtain that the first component of HU : which - is continuous in TA, by Berge's 's Maximum Theorem (1). Applying this argument recursively for ....... 2n. we have that HU (TT,, 21mh) continuous πTA Hence, as Tk, converges to its HU converges to the HU of म. which is Ā. Hence, we continue writing the above derivation as
( (s)(s) (s)) 2 0, by Lemma G.I.
As was arbitrary, the state-value function of the same as that of π. : V = Va. by the Bellman equation 5: (s, a) r(s,a) a) + 7B [V (s')), this also implies that their state-action value functions
30

---

Published as a conference paper at ICLR 2024
the same: ai Qx. Let be the smallest integer such that #3m # mtm. This means that 5mm achieves a greater expected MEHAMO than T Hence,
( am a |
Bg
V (s)
M
Dem
V* (s)
then for some state
M Dem, -1mm-1 V2 (5)
(
>
am mmmmt Fimm- V2 (s)
which can be written
Ea Fiom Low 2im 11 1a wifm
Q (s, 91:m1, aa - log A am (a*m(s) [s)
mm (f |s, Pa.m
Bg Ba- -1 31mm aa Fm mi (8, a #1:m-1 , - a log =m (a²m|p) [s)
mm (# Fm 88
B f1mm- Flom
m (8, a #l:m 1,85m) - a log म Fm (a [s)
2m D
( 88
Flom
n
-garmm-1 91:m-1 am 5m
+ (s, a a am a log म (a²m|s))
Adding both sides of the inequality by Eis H (m (-1s) and using the equation V+(s)
Eash (s, a > H (at (+|s)] gives
(s(s) Eant
Q+ t Σ H (5' (+|))
n
Ea
H (+' (+|s) Q+ (s, + Σ
mm (#*m|s [s, a Rlom-1)
n
Enn
Qx (s, +
Σ H (#' (-|s)
Vs)s
However, we have V = V which yields contradiction, proving the claim.
Step 3: dropping the HADE. Consider an arbitrary limit point joint policy т. By Step 2. for any permutation i1.m, considering the first component of the HU,
[MMon V* (s)
#
arg max Exrggn wit eut (#'1)
arg max Egwan witl ele (R11)
Eg Eaunniis
Q (s, at) a log T (a/1|s) Dtt (r*
arg max Ex- wn el (mi1)
A (s, att) - a log (a (a*) D4 (r)
Suppose that there exists policy n' + #h, and state 8, such that
T' arg max Eatras [A (s,aft) - a log 4 (a [s)]
(30)
wi (xf1)
implies
B (A a"1) a log n' (a*1(s] > Banne (1) a) log क" (s'
which can be written as
Byia (s) all (T' (*1s) tHl (= (*1s))
31

---

Published as a conference paper at ICLR 2024
For any policy T², consider the canonical parameterisation (''(,=10)) = (I,....;Tm- 1 - - 1 ).). where m is the size of the action space. We have that
E Balen [1
Σ T'
(a
A (s, (s)
1:4 (s, (s. + 1 - m-
Σ Ijj
A (s, am
Ij A (s,aat) A (s,
A (s, am))
This means that Eggh with
[A (s, a²1]] is an affine function of TT (.at [s)) and thus, its Gâteaux deriva- tives are constant in P(A) for fixed directions. Hence, we can obtain that Eati [A (s, a²t]] + a'd (Iri (ftls)) is a strict concave function of Tr (f*1(s) (following from the affinity of Eatiwari [4# (s, a²t] and the strict concavity of H. (T" (>*(s)). Therefore, by combining the Equation 30 and the strict concavity of ggunz' [4 (s, a])] + atl (T' (d*[s)). Gâteaux deriva- tive of Eat [4* (s, a")] + aH (I11 (>1s)). in the direction from 7. to TT, is strictly positive.
Furthermore, the Gâteaux derivatives of D' (T' are zero at nt (s)(s)
("1ss) by its defini- tion (zero gradient). Hence, the Gâteaux derivative of Egiroi [A (s, a)] + afd (Tr (.*ls)) # (1**(s) is strictly positive. Therefore, for conditional policies # (s1(s) sufficiently close to n (.") [s) in the direction towards n r((.'11)) [s), we have
E Eatiaf
[ (s. a + all (+') (*118) - D4 2#
(31)
Eat A (8, a(t) + aH (#* (a1s)) D' ( ().
Let us construct a policy H as follows. For all states y + s, we set म' (1'1t) (1(()1 Moreover, for 741 (.21 (s) we choose ***(("1|b)) as in Inequality 31, sufficiently close to म (.51s), so
that 741 E U (#t1). Then, we have
B
AA (s, a") + Eawan at (7* ((11s) D4 (7 (7* [s)]
A
> att AA (s, a Bawga aalt (7 (fL - D (T
(s* [s)]
which yields a contradiction. Hence, the assumption was false. Thus, we have proved that, for every state 8,
# (511)) = arg max Esiiaiis [A (s, a²) - lologg (a" [s)]
a et (#11)
arg max Egioah [Q+ (s, a") a log " (a'ls)] (LEE((())
Step 4: Quantal response equilibrium. We have proved that स satisfies
मं (+1ss)
arg max Egiuo [Q's (s, a²) a log T (a'1s)]
Tं ((1)))(()))
arg max Enina 1Q (s. a)] (1))))P(())))
Σ 1E EA
Σ
n³ (o'ls) log (d)ls),iiEN,
Then following the proof of Theorem 1, we have
exp (a -E,, -En-in i (Qr (s,a¹, a 1))
# (x)) = EveE exp (a- Ea--aa- (Q (s, bi a ")])
inn
32

---

Published as a conference paper at ICLR 2024
Thus, It is quantal response equilibrium. Lastly, this implies that the value function corresponds to a quantal response value function VQRE, the return corresponds to a quantal response return JQRE.
33

---

Published as a conference paper at ICLR 2024
H EXPERIMENTAL DETAILS
H.1 AUTOMATICALLY ADJUSTING TEMPERATURE
We implement an automated temperature tuning method for HASAC which draws on the auto-tuned temperature extension of SAC (9). Thus, adjust with the following objective:
J (a)= = ManrDDaanl--o log π (a))s) atH,,
where H the target entropy.
H.2
EXPERIMENTAL SETUP AND ADDITIONAL RESULTS
H.2.1 BI-DEXHANDS
Bi-DexHands (2) offers numerous bimanual manipulation tasks that are designed to match various human skill levels. Building on the Isaac Gym simulator, Bi-DexHands supports running thousands of environments simultaneously. This increases the number of samples generated in the same time interval, thus significantly alleviating the sample efficiency problem of on-policy algorithms.
We evaluate HASAC on nine tasks simulating human behaviors across different ages and compare it with on-policy algorithms НАРPО, MAPPO, PPO, and off- off-policy algorithms HATD3 and SAC, as shown in Figure 7. Despite leveraging GPU parallelization, we observe that the sample efficiency of on-policy algorithms remains significantly lower than that of off-policy algorithms. In the most challenging Catch Abreast, Two Catch Underarm, and Lift Underarm tasks, on-policy algorithms fail to learn useful policies within 10m steps. While the off-policy algorithm HATD3 demonstrates higher sample efficiency compared on-policy algorithms, it exhibits substantial variance during training due to the deterministic policies it learned, eventually converging to local optima. In contrast, algorithm HASAC outperforms the other five methods by large margin, showcasing faster convergence speed and lower variance.
H.2.2 MULTI-AGENT MuJoCo
MuJoCo tasks challenge robot to learn an optimal way of motion; Multi-Agent MuJoCo (MAMu- JoCo) models each part of a robot as an independent agent, for example, leg for a spider or an arm for swimmer. With the increasing variety of body parts, improving each agent's 's exploration becomes necessary. Although the easier tasks with fewer agents can be solved by a wide range of different algorithms, the more complex benchmarks, such as the HumanoidStandup 17x1 and Many AanntSSentwimmer 10x2, are difficult to solve with current MARL algorithms.
We compare method to several algorithms that show the current faate-of-the-ar performance in 10 tasks of 5 scenarios MAMuJoCo, including HАPPO, a sequential-updatt on-policy algorithm; MAPPO, simultancous-updia on-policy algorithm; and HATD3 (45), off off-policy algorithm that outperforms HADDPG and MADDPG. Figure 8 demonstrates that, in all scenarios, HASAC enjoys superior performance the three rivals both in terms of reward values and learning speed.
H.2.3 STARCRAFT MULTI-AGENT CHALLENGE
StarCraft Multi-Agent Challenge (SMAC) (25) contains set of StarCraft maps in which a team of ally units aims to defeat the opponent team. Notably, MAPPO (42), HAPPO, and HATRPO have demonstrated remarkable performance on this benchmark through the utilization of five influential factors that significantly impact algorithm performance.
We evaluate our method on four hard maps and four saper-hard. Our experimental results, illustrated in Figure 9, reveal that HASAC achieves over 90% win rates in 7 out of 8 maps and significantly outperforms other strong baselines in most maps. Notably, in particularly challenging tasks such as 5m_vs. in__s__ mn__v_6m, 6m, 3s52_vs_ vs_ _s_3, and 6h_ 8z, we observe that HAPPO and HATRPO would converge towards suboptimal NE. addition, FOP is unable to learn meaningful joint policy in super-hane tasks due to its reliance the IGO assumption. By contrast, HASAC consistently achieves superior performance and shows the ability to identify higher reward equilibria due to its extensive exploration. We also observe that HASAC has better stability and higher learning speed across most maps.
34

---

Published as a conference paper at ICLR 2024
56
202
170
422
MARP
HCDD3
224
03
(a) Catch Abreast
(b) Two Catch Underarm
(c) Lift Underarm
StadrafinnDDerr
Gvatiel bnd
Sradesl busseen
25
315
25-
251
FACAC
347
(d) Hand Over
(e) Catch OverUunderarm
(f) Hand Pen
Sieedwer wwwDeerC woetwarrd
Shadivwiter SnudionlladDbwrreee Owsorriwwwrdd
Shacowl Shucowe Bttp://wwwnDrrrrr-----rrr
SCE
HOsGe
300
20p
101
2x5
3dt
200
(g) Door Close Inward
(h) Door Open Inward
(i) Door Open Outward
Figure 7: Comparisons of average episode return on nine Bi- Bi-DexHands tasks.
H.2.4 GOOGLE RESEARCH FOOTBALL
Google Research Football Environment (GRF) contains a set of cooperative multi-agent challenges in which a team of agents plays a team of bots various football scenarios. Recent works (42; 45) have conducted experiments on academic scenarios and achieved nearly 100% winning rate on each scenario except two very challenging tasks: run pass and shoot with keeper (RPS) and corner. We apply HASAC to these two academy tasks of GRF, with QMIX and several SOTA methods, including HAPPO and MAPPO as baselines. Since GRF lacks a global state interface, we propose a solution to address this limitation by implementing global state based agents' observations following the Simple1 15State Wrapper of GRF Concretely, the global state consists of common components in agents' observations and the concatenation of agent-specific parts and is taken as input by the centralized critic for value prediction. Additionally, we employ the dense-reward setting. All methods are trained for 20 million environment steps in the RPS task and for 25 million environment steps in the corner task.
As shown in Figure 10a and 10b, we generally observe that both MAPPO and HAPPO tend to converge to a non-optimal NE on the two challenging tasks with a winning rate of approximately 80%. This suboptimal convergence can be attributed to the insufficient level of exploration of these algorithms. In contrast, HASAC exhibits the ability to attain higher reward equilibrium by learning stochastic policies, which effectively enhance exploration and robustness. This finding highlights the crucial role of stochastic policies in improving exploration, thereby enabling agents to converge toward a higher reward equilibrium.
H.2.5 MULTI-AGENT PARTICLE ENVIRONMENT
We evaluate HASAC on the Spread, Reference, and Speaker_Listener Listener tasks of the Multi-Agent Particle Environment (MPE) (19), which were implemented in PettingZoo (31). PettingZoo incorporates
35

---

Published as a conference paper at ICLR 2024
Ant-2 2x4
Ant-22 4x2
Ant-v2
7000
6000
6000
3000
Epaicde Rat
4000
4200
4002
3000
3000
2000
MAPPO
HATDS
1000
HAPO
4454C
0.5
0.2
0.4
0.6
0..3
1.0
0.0
0..
0.4
0.55
01.3
1.0
0.0
0.2
0.6
2.5
0.5
3.0
Stop
(a) 2x4- Exe-Agent Ant
(b) 4x2-Agenn Ant
(c) 8x1-Agent Ant
HellCheetehhw?
HellCheelahww2 3x2
HellCheeiehww2 6x1
0000
8000
0200
1000
6000
2002
2000
2000
HARRO
01
HAGAC
Step
207
Step
267
Step
(d) 2x3-Agent HalfChectah
(c) 3x2-Agent HalfCheetah
(f) 6x1 -Agent HalfChcetah
Walkerr2d12 2x3
Walker2d-22 6x1
80000
7000
7000
400
6000
0000
5000
200
4200
3000
1000
3000
2000
2000
HATDS
MAPPO
1000
-100
HARRO
0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.0
1.0
0.0
0.2
0.4
0.6
0.8
1.0
(g) 2x3-Agent Walker
(h) 6x 1-Agett Walker
(i) 10x2-Agent Swimmer
@Standup-2 17x1
140000
102000
63000
Step
(i 17x 1-Aent HumanoidStandup
Figure 8: Comparisons of average episode return on multiple Multi-Agent MuJoCo tasks.
MPE with as well as the global and local rewards. To adapt these tasks to fully cooperative MARL settings, sum up the individual rewards of agents to form joint reward. The results presented in Figure 11 shows that HASAC consistently outperforms the baselines in terms of both average return and sample efficiency.
minor adjustments and allows for customizing the number of agents and landmarks,
H.2.6 LIGHT AIRCRAFT GAME
In addition to the previous three well-established benchmarks, we extend our experiments to include novel environment called Light Aircraft Game (LAG) (23). LAG a recently developed cooperative- competitive environment for red and blue aircraft games, offering various settings such as single control, 1v1, and 2v2 scenarios. In the context multi-agent scenarios, LAG currently supports self- play only for 2v2 settings. To address this limitation, we introduce novel cooperative non-weapon task where two agents collaborate to combat two opponents controlled by the built-in AL. Specifically, the agents are trained to fly towards the tail of their opponents and maintain suitable distance.
36

---

Published as a conference paper at ICLR 2024
68
20
(a) 0m-vs-9m (hard)
(b) 5m-vs 6m (hard)
(c) 3s5z (hard)
10m 13m
MANO
165r Jetr
HACAC
025
(d) 10m-vs-1 1 Im (hard)
(e) MMM2 (super hard)
(1) 3852-v8-3s66 (super hard)
corrdor
MURO
0.3
15.50
206
347
280
corridor (super hard)
(h) 6h-vs-88 8z (super hard)
Figure 9: Performance comparison on eight SMAC tasks. We generally observe that HASAC consistently
outperforms other baselines in most tasks, exhibiting higher convergence speed and better stability.
ocademy run pass and shoot with keeger
academy
Non-meapon
1.0
QMXX
0.81
Disl obe Witrinng Dare
0.6-
0.4
0.2
MAPPO
HAPO
0.0
MASAC
0.0
0.5
3.0
1.5
2.0 107
0.0
0.5
1.0
3.5
2.0
2.5
0.0
0.4
0.6
0.8
1.0
Seep
Step
(a) RPS (2 agents)
(b) Corner (11 agents)
(c) Non-weapon (2 agents)
Figure 10: Performance comparison on two GRF tasks and one LAG task. HASAC achieves superior performance the other methods.
We compare our method to MAPPO and HAPPO on the cooperative non-weapon task involving 2 agents. Figure 10c demonstrates that HASAC outperforms both MAPPO and HAPPO in terms of learning speed and stability. Specifically, HASAC exhibits faster convergence and achieves a higher level of stability throughout the learning process. In contrast, MAPPO and HAPPO exhibit considerable variability in their performance and display slower learning speeds.
H.3 HYPER-PARAMETER SETTINGS FOR EXPERIMENTS
Before presenting the hyperparameters employed in experiments, would like to clarify the reporting conventions we adhere to. First, we introduce a boolean variable auto alpha to indicate whether the temperature is auto-tuned not. Also, the hyperparameters will only take effect when
37

---

Published as a conference paper at ICLR 2024
Reference rontrn
Spross fortinussst
Cplce Deturm
-20
MANTO
-10
(a) Reference (continuous)
(b) Speaker Listenor (continuous)
(c) Spread (continuous)
Szenker
Sprwad ncmeee
-25
NE HANAT
-24
Spauck
(d) Reference (discrete)
(e) Speaker Listener (discrete)
(f) Spread (discrete)
Figure 11: Comparisons of average episode return on six MPE tasks.
they used. For instance, the temperature parameter taken into consideration only when the boolean value auto_ auto_alpha is set to False. Similarly, the prrgeteenropy and alpha Ir are applicable when auto _att_aa is set to True.
be assigned any numerical value, but it
H.3.1 COMMON SYPER-PARAMETERR ACROSS ALL ENVIRONMENTS
We implement the HASAC based on the HARL framework (45) and employ the existing implemen- tations of other algorithms, including HATD3, HAPPO, HATRPO, and MAPPO, as described in the HARL literature. In Google Research Football, we use the results of QMIX in Yu et al. (42). In StarCraft Multi-Agent Challenge, we use the results of FOP Zhang et (44). To ensure comprehensive evaluation, conduct training using minimum of four different random seeds for each algorithm. Next, we offer the hyperparameters used for HASAC in Table 4 across all environments, which are kept comparable with the HATD3 for fairness purposes.
Table Common hyperparameters used for off- policoliy algorithms HASAC HATD3 across all environments.
hyperparameters
value
hyperparamerters
value
proper time limits
True
warmup steps
1e4
activation buffer size
ReLU
final activation
Tanh
le6
polyak update per train
0.005
hidden sizes
[256, 256]
train interval
50
target entropy
-di((A')
policy noise
0.2
noise clip
0.5
policy update frequency
linear decay
False
H.3.2 BI-DEXHANDS
In the Bi-DexHands domain, for SAC, PPO, MAPPO baselines we adopt the implementation and tuned hyperparameters reported in the paper (43). And for HAPPO we adopt the implementation and tuned hyperparameters reported in the HARL paper (45). Here we report the hyperparameters for HASAC and HATD3 Table and 6.
H.3.3 MULTI-AGENT MuJoCo (MAMUJOCO)
In this part, report the hyperparameters used in MAMuJoCo tasks for HASAC and HATD3 in Table 7, 8, 9, and 10. For the other three baselines, we utilize the implementation and tuned hyperparameters reported in the HARL paper (45).
38

---

Published as a conference paper at ICLR 2024
Table Common hyperparameters used for HASAC and HATD3 in the Bi-DexHands domain.
hyperparameters
value
hyperparameters
value
hyperparameters
value
rollout threads
20
gamma
0.95
batch size
1000
actor Ir use huber loss
5e
critic Ir
5e 4
step
20
False
use valuenorm
False
exploration noise
0.1
Table 6: Different hyperparameters used for HASAC in the Bi-DexHands domain.
scenarios
auto alpha
alpha
alpha
HandowHannCCtcchAAe
True
3e
Shadow Two Underaar
False
5e 5
True
30
ShadowHanddOver
True
3e 4
ShadowHaanCCcchhhoee22ddeeded
True
ShadowHandPen
True
3
ShadowHHanddDoorrtooosnnvaaa
True
3
ShndowwHannDDorrOpelllaaaa Shaddow.HanddDoorrppeaattttttt
True
3e
True
3e
Table 7: Common hyperparameters used for HASAC and HATD3 in the MAMuloCo domain.
hyperparameters
value
hyperparameters train interval
value
rollout threads
10
50
critic
1
gamma use valuenorm
0.99
use huber loss
False
False
Table 8: Common hyperparameters used for HATD3 in the MAMuJoCo domain.
hyperparameters
value
hyperparameters value
actor Ir
5e
exploration noise 0.1
Table 9: Parameter n_step used for HASAC and HATD3 in the MAMuloCo domain.
scenarios Ant 2x4
value
scenarios
value
HalfCheetah 2x3
10
Ant 4x2
5
HalfCheetah 3x2
10
Ant 8x1
5
HalfCheetah 6x
10
Walker 2x3
20
Walker 6x1
20
manyagent swimmer 10x2
10
HumanoidStandup 17x1
10
Table 10: Different hyperparameters used for HASAC in the MAMuJoCo domain.
scenarios
actor Ir
auto alpha
alpha
alpha Ir
batch size
Ant 2x4
3e
False
0.2
2200
Ant 4x2
30 4
False
0.2
1000
Ant 8x1
3
False
0.2
2200
HalfCheetah 2x3
le-3
True
3e 4
1000
HalfCheetah 3x2
1e-3
True
3e
1000
HalfCheetah 6x1
1e-3
True
3e 4
1000
Walker 2x3
5e
False
0.2
1000
Walker 6x
5e-4
False
0.2
1000
manyagent swimmer 10x2
le-3
True
3e
1000
HumanoidStandup 17x1
1e-3
True
3e
1000
H.3.4 STARCRAFT MULTI-AGERS CHALLENGE (SMAC)
In the SMAC domain, for MAPPO we adopt the implementation and tuned hyperparameters reported in the MAPPO paper (42). And for HAPPO and HATRPO adopt the implementation and tuned
39

---

Published as a conference paper at ICLR 2024
Table 11: Common hyperparameters used for HAPPO and MAPPO in the MAMuloCo domain.
hyperparameters value
hyperparameters
value
batch size
4000
network
MLP
gamma
0.99
hidden sizes
[256, 256]
Table 12: Different hyperparameters used for HAPPO and MAPPO in MAMuloCo domain.
linear
actor/critic
ppo/critic epoch
clip param
actor/critic mini batch
entropy coef
scenarios
Ir decay
Ant HalfCheetah
False
Se
0.1
0
False
-
15
0.05
0.01
Walker 2x3
True
le-3
0.05
0
Walker 6x1
False
5e
5
0.1
1
0.01
manyagent swimmer 10x2
False
5
0.2
0.01
HumanoidStandup 17x1
True
5
5
0.1
0
hyperparameters reported in the HARL paper (45). Here we report the hyperparameters for HASAC in Table 13 and 14.
Table 13: Common hyperparameters used for HASAC the SMAC domain.
hyperparameters
value
hyperparameters
value
hyperparameters
value
rollout threads
20
state type
FP
batch size
1000
use huber loss
False
use valuenorm
False
use policy active masks
true
Table 14: Different hyperparameters used for HASAC in the SMAC domain.
auto
Map
critic
actor
gamma
alpha
alpha
alpha
n step
8m_vs. v__
-
3e -4-4
0.95
True
3
5
5m vs. 6m
5
3e-4 4
0.95
True
/
-
20
3s5z
5
3
0.99
True
/
3
20
vs_
-4
0.95
True
3e
20
MMM2
5e-4
34-4
0.95
True
3e-4 4
20
3s5z_vs. _s__v____s_ vs_3s6z
5
34-4
0.99
True
3e-4
10
corridor
5e-4
5e-4
0.99
False
2
5
6h_vs_88 8z
5
34-4
0.99
True
3e
5
H.3.5 GOOGLE RESEARCH FOOTBALL (GRF)
In the GRF domain, for MAPPO QMIX baselines we adopt the implementation and tuned hyperparameters reported in the MAPPO paper (42). And for HAPPO adopt the implementation and tuned hyperparameters reported in the HARL paper (45). Here we report the hyperparameters for HASAC in Table 15 and 16.
Table 15: Common hyperparameters used for HASAC in the GRF domain.
hyperparameters
value
hyperparameters
value
hyperparameters
value
rollout threads
20
gamma critic Ir
0.99
batch size
1000
actor Ir use huber loss
5e 4 False
5e
step
10
use valuenorm
False
Table 16: Different hyperparameters used for HASAC in the GRF domain.
scenarios
auto alpha
alpha
alpha Ir
RPS
False
1c-4
Corner
False
lc 3
40

---

Published as a conference paper at ICLR 2024
H.3.6 MULTI-AGENT PARTICLE ENVIRONMENT (MPE)
In this part, we report the hyperparameters for HASAC in Table 17.
Table 17: Hyperparameters used for HASAC in the MPE domain.
hyperparameters
value
hyperparameters
value
hyperparameters
value
rollout threads
batch_ssi size
1000
critic Ir
5e
gamma
0.99
actor Ir
5e 4
n s_step
20
auto alpha
True
alpha
3e
huber loss
False
valuenorm
False
H.3.7 LIGHT AIRCRAFT GAME (LAG)
In this part, we report the hyperparameters for HASAC in Table and the hyperparameters for MAPPO and HAPPO in Table 19.
Table 18: Hyperparameters used for HASAC in the LAG domain.
hyperparameters
value
hyperparameters
value
hyperparameters
value
rollout threads
20
batch size
1000
critic Ir
5e
gamma
0.99
actor Ir
5e 4
n_step
10
auto alpha
True
alpha
3e-4
Table 19: Hyperparameters used for MAPPO and HAPPO in the LAG domain.
hyperparameters
value
hyperparameters
value
hyperparameters
value
batch size
4000
linear Ir decay
False
hidden sizes
[256, 256]
actor/critic Ir
5e 4
gamma
0.99
network
MI.P
ppo epoch
entropy coef
0
clip param
0.05
critic epoch
actor mini batch
2
critic mini batch
2
41

---

Published as a conference paper at ICLR 2024
I ABLATION STUDY ON SEQUENTIAL UPDATES
In this section, we conduct an ablation study to investigate the effect of sequential updates. We compare the performance of the original HASAC with sequential update scheme, and HASAC without sequential updates (or MASAC), which updates each policy according to the following objective:
)
Jz (6') EeDDD
log (a/)st) Ouaa .0 (ot, al. a,
We run the experiments on nine HanDe tasks. For a fair comparison, we set the hyperparameters of MASAC to be the same those of HASAC. Experiments results show that HASAC with sequential updates consistently achieves better performance.
Tasks
HASAC
MASAC
Shadow
45.9(4.3)
36.4(5.2)
20.6(1.9)
17.2(1.1)
Shadow ShadowHandl Lf
361.0(23.2)
345.0(9.7)
Shadow HandOver
31.1(0.7)
30.5(1.1)
28.7(0.4)
27.0(0.9)
ShadowHandPP
181.5(10.4)
163.8(18.6)
ShandowwHanddooooCCseeaaaaad
429.8(16.7)
425.9(7.1)
ShadowHHandDoorrrpeennnwaaa
475.6(23.8)
428.8(14.1)
ShadoowwHandDoonroheeootttvaaa
542.1(13.1)
528. 120.4()0.4)
Table Averaged final performance on Bi-DexHands tasks.
42


Reviews:
[{"review_id": "pX8TiasVf0", "reviewer": "Reviewer_YGsv", "summary": "This paper considers the problem of co-operative Multi-Agent Reinforcement Learning, where issues of sample complexity, training instability, and sub-optimal exploration affect leading methods. The authors propose a method for learning stochastic policies to overcome these limitations, by drawing a connection with Graphical models and deriving a familiar Maximum Entropy solution optimization approach.\n\nThe paper is well written, seems comprehensive in it's theoretical establishment of the new method, and thorough in the range of depth of empirical evaluations.\n\nI am familiar with single-agent RL (and have a background in Inverse Reinforcement Learning theory), however am only tangentially aware of work in the multi-agent RL setting. As such, I may have overlooked details or not been aware of relevant prior work when reviewing this paper. I have read the paper, and skimmed the appendices, however did not do a detailed check of the proofs.", "questions": "# Questions and comments\n\n* It seems the design of the drift functional and neighborhood operators will be key to the success of the proposed HASAC, or MEHAML based methods (as you note in Sec. 6). Can you provide any comment on what factors should be taken into consideration in the construction of these terms? E.g. in what ways will this depend on the nature or definition of the MARL task? Some discussion of the design/selection of these terms for your empirical experiments might be helpful here.\n * The core method (e.g. end of Sec.4 on p7) seems to have high-level similarities to PPO methods for single-agent RL (e.g. constraint to keep the policies from drifting too far) - do you see any connection to this family of methods? Is this something that could be explored further in the literature or has been already?\n * The notion of Quantal Response Equilibrium is key to this optimization objective, but I'm not familiar with this term. You provide a citation (#20, also #6), but the paper would be strengthened with a little bit more explanation of this notion in Sec 4.1. E.g. can you give some intuition for what this objective means in practice compared to regular Nash Equilibrium? In what situations is QRE to be preferred over NE?\n * What is the $\\omega$-limit (Point 4 in Theorem 3) - I could not find a definition and am not familiar with this terminology.\n\n# Minor and grammatical points\n\n * Under heading 5.1 - '2 hundred' - could write as '200'\n * There are a lot of acronyms in this paper - please consider adding a table of acronym definitions in the appendix to aid readers.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Well written, easy to follow the argument development. Seems to engage thoroughly with prior work.\n * Empirical evaluations are strong, and results support the conclusions", "weaknesses": "* The contribution of the method in part hinges on the limitations induced by the 'IGO' assumption from prior work (Sec 2, p2), but this is never elaborated on in the paper. Can you define IGO more clearly and explain exactly what limitations this assumption introduces? This will help the reader not intimately familiar with MARL.\n* The proposed methods introduces hyper-parameters, notably the temperature term $\\alpha$ and the drift functional and neighborhood operator. However any alternate method will also have hyper-parameters, so this isn't a big drawback. Some elaboration of the 'automatically adjusted' $\\alpha$ schedule (citation #9) just before the heading for Sec. 6 might be helpful for the reader here.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qe77jl5L5V", "reviewer": "Reviewer_ZAWK", "summary": "The authors propose a novel algorithm, Heterogeneous-Agent Soft Actor-Critic (HASAC), based on the Maximum Entropy (MaxEnt) framework. The paper theoretically proves the monotonic improvement and convergence properties of HASAC to a quantal response equilibrium (QRE). The authors also introduce a generalized template, Maximum Entropy Heterogeneous-Agent Mirror Learning (MEHAML), which provides any induced method with the same guarantees as HASAC. The proposed methods are evaluated on six benchmarks, demonstrating superior performance in terms of sample efficiency, robustness, and exploration.", "questions": "1. Could the authors provide more details on how sensitive is the performance of HASAC to the choice of α?\n2. How does the proposed method perform in scenarios where sample efficiency is crucial? Could the authors provide experimental results in such scenarios?\n3. Could the authors provide more comprehensive experimental results, including results from a larger number of seeds ?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-structured and clearly written, making it easy to follow the authors' line of thought.\n2. The authors provide a comprehensive theoretical analysis of the proposed methods, including proofs of monotonic improvement and convergence to QRE.\n3. The proposed methods are evaluated on a variety of benchmarks, demonstrating their versatility and effectiveness.", "weaknesses": "1. The novelty of the paper is limited, as the main contribution is the application of the Soft Actor-Critic (SAC) algorithm to the multi-agent setting.\n2. The authors should have tested their method in scenarios where sample efficiency is crucial (such as real robots, stock exchange, etc), given that their proposed method is off-policy.\n3. The validity of the experimental results is questionable. The training curves show significant fluctuations, and the authors only present a selection of results in the main paper, which may give a biased view of the method's performance.\n4. The authors should provide more comprehensive experimental results, including results from a larger number of seeds, to fully demonstrate the effectiveness of their method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OTR5luNcIc", "reviewer": "Reviewer_iakN", "summary": "This paper proposes a MaxEnt MARL approach that employs sequential policy updates and uses a centralized Q-function. They provide the representation of QRE policies maximizing the MaxEnt objective of MARL and demonstrate that the joint policy updated through the sequential policy updates converges to the joint QRE policy. The proposed practical algorithm is simple and outperforms the baselines on various benchmarks.", "questions": "For the weaknesses, could you provide results of MASAC, which is the HASAC without the sequential policy updates, on the benchmarks and the idea of an adaptive entropy temperature tuning method for better exploration?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1.\t(Theoretical) With the multi-agent soft Q-value function defined in the main paper, the authors demonstrate that through the sequential policy updates, the joint policy converges to a QRE policy while monotonically improving the objectives for the policy and Q-value function.\n\n2.\t(Contribution) The authors provide remarkable combinations for the MaxEnt problem of those that exist in previous works; the monotonic improvement and the convergence to a QRE policy for the MaxEnt objective seem to be rigorous, and they extend the MaxEnt MARL problem to the general one with possible constraints.\n\n3.\t(Simplicity) The proposed practical algorithm is straightforward. The algorithm doesn’t require recomputing Q-value estimation for the sequential policy updates.\n\n4.\t(Experimental) On a bunch of benchmarks, the proposed algorithm consistently achieves superior performance and high sample efficiency, compared to the baselines.", "weaknesses": "1. (Unclear effect of the sequential updates) Although there is an example [1] to show why the sequential policy updates for the standard MARL objective are needed, an example or technical explanation for the MaxEnt MARL objective is also needed. It is because the authors define the multi-agent soft Q-function (eq. (7)) and local policy update (eq. (8)). Also, the practical objective for the policy (eq. (10)) can be reduced to the expectation of $\\alpha\\log\\pi_{\\phi_{i_m}}^{i_m}-Q_{\\pi_{old}}^{i_{1:n}}$, which is consistent with the pseudocode of HASAC, since the MA soft Q-function consists of the centralized Q-function $Q_{\\pi_{old}}^{i_{1:n}}$ and the entropy term of its complementary agents, which is not subject to optimize. So, in the proposed algorithm, the sequential policy update may be just additional sampling actions of some agents.\n\n2. (Sensitive to the entropy temperature) The Ablation study shows that the proposed algorithm may not be robust to the entropy temperature and converge to different policies according to the temperature. In this paper, each domain has a different entropy temperature; one domain has a fixed temperature, and another has an automatic temperature with a fixed target entropy. A more effective method to tune entropy terms is needed, like ADER[2].\n\n[1] Kuba et al., Trust Region Policy Optimisation in Multi-Agent Reinforcement Learning, ICLR 2022.\n\n[2] Kim et al., An Adaptive Entropy-Regularization Framework for Multi-Agent Reinforcement Learning, ICML 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ILVMilGTaN", "reviewer": "Reviewer_9JkX", "summary": "This work addresses cooperative multiagent reinforcement learning (MARL). It builds on the idea of MaxEnt RL, and proposes the maximum entropy heterogeneous-agent reinforcement learning (MEHARL) framework for learning stochastic policies in MARL. On the theoretical/technical side, it uses the PGM to derive the MaxEnt MARL objective, and prove monotonic improvement and QRE convergence properties for the corresponding HASAC algorithm, as well as the unified MEHAML template. On the empirical side, HASAC has been implemented on six benchmark MARL tasks and it achieves the best performance in 31 out of 35 tasks across all benchmarks.", "questions": "The MEHAML framework (or HASAC) is proved to converge to QRE, but not the optimal NE. But it seems that empirically HASAC does learn a good equilibrium due to the stochastic policies. I am curious if is it possible at all to have some sort of guarantees to reach the optimal NE?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Excellent presentation. The methodology is well motivated with an illustrative matrix game example. The related work is well discussed and the contribution of this paper is clear. The paper is overall well structured and easy to follow. \n\n2. Clear technical contribution. The algorithmic framework MEHAML as well as the specific practical algorithm HASAC are novel and theoreticall grouned with proofs on the nonotonicity improvement and convergence to QRE. The method is not a simple combination of MaxEnt RL and MARL, but the derivation of the MARL version is built on the PGM formulation connecting from the idea of control as an inference task.\n\n3. Superior empirical performance over a wide spectrum of benchmark tasks -- HASAC has been implemented on six benchmark MARL tasks and it achieves the best performance in 31 out of 35 tasks across all benchmarks.", "weaknesses": "I don't see a major weakness. \n\nA minor point: the IGO assumption is not explained when first being introduced. I don't think people outside MARL are familiar with this term.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)