Pareto Actor-Critic for Equilibrium Selection in Multi-Agent Reinforcement Learning
Authors: Filippos Christianos
Georgios Papoudakis
Stefano V Albrecht
Venue: Accepted by TMLR ()

Abstract: This work focuses on equilibrium selection in no-conflict multi-agent games, where we specifically study the problem of selecting a Pareto-optimal Nash equilibrium among several existing equilibria. 
It has been shown that many state-of-the-art multi-agent reinforcement learning (MARL) algorithms are prone to converging to Pareto-dominated equilibria due to the uncertainty each agent has about the policy of the other agents during training. To address sub-optimal equilibrium selection, we propose Pareto Actor-Critic (Pareto-AC), which is an actor-critic algorithm that utilises a simple property of no-conflict games (a superset of cooperative games): the Pareto-optimal equilibrium in a no-conflict game maximises the returns of all agents and, therefore, is the preferred outcome for all agents.
We evaluate Pareto-AC in a diverse set of multi-agent games and show that it converges to higher episodic returns compared to seven state-of-the-art MARL algorithms and that it successfully converges to a Pareto-optimal equilibrium in a range of matrix games. Finally, we propose PACDCG, a graph neural network extension of Pareto-AC, which is shown to efficiently scale in games with a large number of agents.

Published in Transactions on Machine Learning Research (10/2023)
Pareto Actor-Critic for Equilibrium Selection in Multi-Agent Reinforcement Learning
Filippos Christianos
f.christianos@ied.cco uk
University of Edinburgh
Georgios Papoudakis University of Edinburgh
9- pepoudakis@edd.co uk
Stefano V. Albrecht
s. s.albrecht@ed.ccom uk
University of Edinburgh
Reviewed on OpenReview: htips: // openreview. net/ met/ forum? id- 3Azq 1818
Abstract
This work focuses on equilibrium selection in no-conflict multi-agent games, where we specif- ically study the problem selecting a Pareto-optimal Nash equilibrium among several ex- isting equilibria. It has been shown that many state-of-the-art multi-agent reinforcement learning (MARL) algorithms are prone to converging Pareto-dominated equilibria due to the uncertainty each agent has about the policy of the other agents during training. To address sub-optimal equilibriun selection, we propose Pareto Actor- ic (Parelo-AC), which is an actor-critic algorithm that utilises simple property of no-conflict games (a superset of cooperative games): the Parcto-optimal equilibrium in a no-conflict game max- imises the returns of all agents and, therefore, is the preferred outcome for all agents. We evaluate Pareto-AC in a diverse set of multi-agent games and show that converges to higher episodic returns compared to seven state-of-the-art MARL algorithms and that it successfully converges Pareto-optimal equilibrium in range of matrix games. Finally, propose PACDCG, graph neural network extension of Pareto-AC, which is shown to efficiently scale in games with a large number of agents.
1 Introduction
Multi-Agent. Reinforcement Learning (MARL) in no-conflict garne (a superset of cooperative games, detailed below) aims to jointly train multiple agents to solve a common task in shared environment. Recent work has focused on value decomposition (Rashid al. 2018), communication (Foerster et al. 2016 Wang al. 2020 agent modelling (Albrecht & Stone 2018), experience experience/parrameerr parameter sharing (Christianos et al.) 2020
2021 and more. However, we will discuss, many of these approaches do not differentiate between multiple Nash equilibria, and are prone to converging to sub-optimal solutions.
Consider the Stag Hunt game (Fig, []. two-agent no-conflict game characterised by a shared set of most- preferred outcomes for all agents (Rapoport) 1966). The Stag Hunt game exhibits two pure-strategy Nash equilibria, one of which is Pareto-optimal and the other is Pareto-dominated, also known as the risk-averse equilibrium (Harsanyi & Selten) 1988 Although the Parelo-optimal equilibrium yields the highest returns for all agents, the risk-averse equilibrium is commonly chosen when there is uncertainty regarding the other agent's ' actions. In this context, risk refers to the possibility of inadvertently selecting joint action that incurs penalties. The study of Papoudakis et al. (021)) showed that many recent MARL algorithms are
* "Equal Contribution.
The Stag Hunt game also has one mixed-strategy Nash equilibrium. However, no-conflict games always have pure-strategy Pareto-optimal Nash equilibria. For this reason, the text, we focus our explanations on pure-strategy equilibria.

---

Published in Transactions on Machine Learning Research (10/2023)
Agent 2
A
B
A
(4, 4)
(0, 3)
Agent
B
(3,0) 0)
(
Figure 1: Normal-form of the Stag Hunt game. The game has two pure Nash equilibria, one that is Pareto- dominated (risk-averse) and one that is Pareto-optimal,, In this example, if agent 1 chooses action A, it risks receiving zero reward if the other agent chooses B. But, if agent 1 chooses action B it will always receive a reward of at least 2.
unable to converge to the Parelo-optimal equilibrium in the Penalty and Climbing matrix games (both of which share a similar structure to the Stag Hunt example) used by Claus & Boutilier (1998). We corroborate these findings by showing the tendency of MARL algorithms to converge to a risk-averso equilibrium in stateless matrix games. Furthermore, we show that this behaviour can extend to sequential state-based games if they contain sub-optimal equilibria in the form of penalties for failing to coordinate.
The reason that MARL algorithms, such QMIX (Rashid et al., 2018 or MAPPO Yuu et al. 2021 converge to Pareto-dominated equilibria is rooted in the exploration policies used to explore the stale-action space (e.g., using <-greedy or soft policies). For instance, policy gradient algorithms sample actions from the stochastic policy they learn. When the training starts, the stochastic policies are almost uniform, and often dominated by an entropy term used to promote exploration (Mnih et al. 2016). Therefore, during the early stages of training, algorithms that do not consider the joint action value may assign higher expected returns individual actions that do not require coordination. To illustrate this point, let us consider again the Stag Hunt example where agent 2 is initialised with uniform policy. In this scenario, the expected reward for agent 1 selecting action A is 4 x 0.5 + x 0,5 2, while for action B, it is 3 0.5 + 2 x 0.5 2.5. Consequently, when applying the policy gradient, agent 1 learns to assign a greater probability to action B. This reinforcement further strengthens the risk-averse (B, B) equilibrium through a positive feedback loop, making action A even less appealing for agent? 2.
We propose an algorithm, called Pareto Actor-Critte (Pareto-AC) which is designed to converge to pure- strategy Pareto-optimal Nash equilibria in no-conflict games. The algorithm leverages the characteristic of no-conflict games, where all agents aware that the Pareto-optimal equilibrium also preferred by all the other agents, thus avoiding the drawbacks associated with exploring risky joint actions. To do so, the algorithm guides the policy gradient to the Pareto-optimal equilibrium by using modified advantage estimation that takes inlo account the no-conflict nature of the studied games, assuming each agent expects others to select actions leading to the same equilibrium. To accomplish its goal, the Pareto-AC algorithm performs computations involving joint actions, which scale exponentially with the number of agents. To address this scalability issue, we also explore the use of tractable graph- based approximations (Böhmer al., 2020). This approach leads to propose the Pareto Actor-Crild with Deep Coordination Graphs (PACDCG) extension, which aims to attain comparable outcomes (achieving the second- highest returns in the tested games, after Pareto-AC) while miligaling the scalability concern.
In summary, we contribute a novel deep MARL algorithm which i) successfully converges to Pareto-optimal pure Nash equilibria in all 21 distinct 2 x 2 no-conflict matrix games (Rapoport 1966) and three larger matrix-games (Claus & Boutilier 1998), ii) learns to coordinate in partially observable stochastic games and is the only algorithm (compared to seven state-of-the-ars MARL algorithms) that solves all three proposed high dimensional multi-agent tasks, iii) adheres to the Centralisod Training Decentralised Exccution (CTDE) paradigm that is commonly used in MARL research, and iv) can relax ils scaling properties using the proposed PACDCG graph-based approach.
IImplementation code Pareto-AC can be found in
2

---

Published in Transactions on Machine Learning Research (10/2023)
2 Technical Preliminaries
2.1 Partially Observable Stochastic Games
We consider Partially Observable Stochastic Game (POSG) Hansen et al. 2004 which is defined by D,P, R), where I is the set of N agents i E A A x.. XAN the set of joint actions, where A, is the action set of agent i, O = Oix... max....x . XON N the joint [0, 1] and P P
......,,,, S is the set of states of the game,
obscrvation set, where O the observation set of agent i. Ω: S A define probability distributions over the next joint observation and next state, respectively, given the current state and joint action. Finally; : x A x RN is the reward function that returns a reward rf for each agent i at time step A solution to game is joint policy, π (TI, 7 AN), which satisfies certain requirements expressed in terms of the expected return for each agent. The expected return for an agent under a joint, policy и and the state transition distribution is given by Gi(z) = EEE ""r/[T,
+ [0, 1]
T- where Y E [0, 1] is the discount factor, and H the horizon of the episode. The notation T-; is used to refer to the policies of the other agents such that π = (TT, m-1).
In this work, specifically study no-conflict gomes, in which all agents have the same set of most preferred outcomes. Specifically, in no-conflict games, the agents have the same set of joint policies that maximisc their expected returns, formally:
arg max GT(T) arg max (T(T)) Vi,j EI
A subset of no-conflict games, which extensively studied in the community, are the cooperative games which the reward is common among the agents, i.c. G1 G2 _... G, for any joint policy.
2.2 Game Theory and MARL Solution Concepts
Game theory and MARL are related topics which study how agents can make strategic decisions. While game theory and MARL use different terminology, in this work we adopt MARL's terminology given the main focus of the paper.
Definition 1 (Best-Response). The set of best-response policies for agent i is defined as
BR((TT-)- -arn-m)aaamaaa max T-;)
(2)
Definition (Nash Equilibrium). joint policy n is a Nash equilibrium if there is no agent that can achieve higher expected return by unilaterally changing its policy. The Nash equilibrium can also be written using the best-response (BR), such that joint policy π (T, R-)) is a Nash equilibrium if:
mi E (T.(T=)) V
Definition (Pareto Optimality). A joint policy æ is called Parelo-optimal if no agent can improve ils expected return without making the expected return of another agent worse. Formally, a joint policy is Poreto-optimal if:
هn' such that Vi: G((T)) 2 GT(T) and 3i: G((T') > G.(T)
(4)
If such joint policy n' does indeed exist, then it is said that is Pareto-dominated by n' If joint policy is a Nash equilibrium and Pareto-optimal, we will refer is as Pareto-optimal equilibrium.
2.3 Policy Gradient and Actor-Critic
Policy gradient methods aim to find the parameters & of the parameterised policy Ty that maximise the expectation, under the parancterised policy, of the discounted episodic sum of rewards. The simplest policy gradient method is REINFORCE. (Wiliiams) 1992), which, in single-agent RT, estimates the gradient of the
3

---

Published in Transactions on Machine Learning Research (10/2023)
objective (()) = Ex [G'V Ta(a'(o")) where G is the Monte-Carle return estimation, and of the history of observations. To minimise the variance of the gradient est.imation in REINFORCE, it is common to (i) subtract the state value from the returns, and (ii) approximate the returns using the state value function. Therefore, there is also the need to learn a function that approximates the state value function Vo with parameters 0. The class of algorithms that learn both a policy and a value function is called actor-critic. A commonly used actor-critic algorithm advantage actor-critic (A2C) (Mnih et al., 2016). An application of A2C in MARL is the Independent A2C (IA2C) algorithm, where each agent trained by using A2C and ignoring the presence of the other agents in the environment, with the actor of agent i minimising:
((dx) -aftrm ~ loo (aalo" (1) +o :0,) V 0,)),
(5)
and the critic of agent minimising:
((0.) = Batmasial
, -,,,,, +o ++1 ;0) - v(oi
(6)
Centralised Training Decentrulised Execution (CTDE) is a multi-agent paradigm that involves the sharing of information among agents during training, while ensuring that once the training is complete, agents can execute their policies based solcly on their own observations. Various CTDE extensions of independent actor- critic methods have been proposed in the literature (Lowe et al. 2017 Foerster et al., 2018), wherein the critic is conditioned on the joint trajectory of all agents to enhance the approximation of the expected return for each agent. The centralised training variant of Independent Advantage Actor-Crite (IA2C), commonly referred to MAA2C (Papoudakis et al. 2021] Central-V (Foerster et al.) 2018 in the literature, is trained to minimise the following loss function for the actor:
[((x))
(og -
(7)
and for the critic:
[(0.) Ea (++ -
(8)
for each agent i. The critic in MAA2C utilises the fully observable state 8t, which can also be approximated the concatenation of observations from all agents. Recently, Lyu et al. (2023) discussed how centralised critics conditioned on the state can introduce bias and variance to their estimation. However, this concern can be alleviated by ensuring that the state st includes all the information of the history of observations o or by using recurrent critics (i.e. the critic being conditioned on s²1t). Throughout the document, we will adopt the notation of using state sf as an imput to the critic networks, while the actor networks will take the individual agent history of obscrvations ot as inputs, thus adhering to the principles of CTDE.
3 Pareto Actor-Critic
3.1 Optimisation Objective
Revisiting the Stag Hunt game of Fig. D we observe that agents can reach the desired Pareto-optimal equilibrium if they coordinate. If we assume that it is known by both agent that the other agent is not going to deviate from this equilibrium, then they can both select action A. This can be formally understood by the nature of no-conflict games (Eq. D and that the joint policy that maximises the expected return of one agent, maximises the returns of all agents as well.
We make use of this property of no-conffict games in Pareto-AC while preserving the decentralised interaction of each agent with the environment. For policy n, of agent i, let x be in the set of policies of other agents -i that maximise the returns of agent
* J E arg max GT(TT, mi))
Learning an agent policy n. by maximising G;, given that the other agents follow x_,, leads to joint policy n + +t) that maximises the returns of agent However, from the definition of no-conflict games, that
4

---

Published in Transactions on Machine Learning Research (10/2023)
org max Q a.
ag a
computes
Environment
simulated Irajectories of, of als7' 7",
iT
TD-loss (Eq. 18) to learn Q
new batch
dimension
Policy Gradient (Eq. to lear
Ya., E A. A1 Ag... Age...
Figure 2: High-level overview of Pareto-AC. Trajectorics are collected by simulating agents in an environment (left). The policy mi, is approxinated by evaluating all the joint actions of other agents (i.e. all a- A- with the argmax operator the joint Q value. x can be used to train Q (Eq. 18), which in turn be used in the policy gradient of Parelo-AC (Eq. 15 Pareto-AC trains all agents using the same algorithm.
is also the joint policy that maximises the returns of any other agent in I. Pareto-AC learns such policy for each agent, replacing the typical Nash equilibrium solution (Fq. 3 with:
Hy E arg max (T +
(10)
In practice, during exploration the trajectories are gathered using the joint policy * = (mi, T-:),
while we
optimise the joint policy न (Tg TT)) A high-level outline of Pareto-AC presented in Fig. individual components presented below. This is the standard settings of off-policy actor-critic
while
Degris
et al. 2012 We propose similar objective in our settings:
J(o)) = Σ d" ds)(s) (s)).
(11)
SES
where V. is the state value function of agent i under the joint policy x+ (m, rig,, and d" is the on-policy distribution of the environment's states under the joint policy æ (T.,
3.2 Defining the Pareto Actor-Critic Algorithm
Our proposed algorithm aims to optimise the objective given in Equation using an off-policy actor-critic method. Note that during training one would not have samples from the state distribution d=t. but from the state distribution d= (recall that ı is the joint policy). Building on the work of Degris al. (2012) wo
have that:
VJ(6.) Σ d" (s)
Σ Vxt
(als)))) (s,
Σ (s) Σ (a (=) (s, (s,a;,a_i)
(12)
Σ (s) Σ
a, Vlggmmaal (s,a,,
The approximately equal sign (>) is included because the gradient of the Q-value Q with respect to the parameters is ignored. In their Theorem and 2, Degris et al. (2012) have shown that following the estimated gradient of Equation 12), assuming a sufficiently small learning rate and that the policy is represented in a tabular form, results in improving the objective. Assuming the two joint policies aotd and at before the update, and after Tnew and - it stands that:
Σ Fold (s)[V (s)] 2 Σ Fote (s) (s))
(13)
5

---

Published in Transactions on Machine Learning Research (10/2023)
T2 = U
Agent
Agent
B
2.5
B
3
(a) Expected reward for agent 1 in the Stag Hunt game given that agent follows a uniformly random policy (2()) = 0.5 and (B) = 0.5. While the Pareto-optinal joint action is (A, agent 1 would expect a higher re- ward if it selects action B. This further reinforces agent 2 to also prefer action B leading to the sub-optimal equi- librium (B.
(b) Expected reward for agent 1 in the Stag Hunt game given that agent 2 follows the m. where n. (4) = 1.0 and (B) = 0. If agent 2 follows policy m agent 1 will prefer action A. This will lead agent to prefer action A too, which will lead to the Pareto-optimal joint-action AA,
Figure 3: Expected return for agent under the expectation that agent 2 is using uniform policy (in a), and the policy x+ (in b).
Additionally, the gradient update results increasing the state value function for every state:
new (s) 2 vi
E
(14)
Below, we rewrite the optimisatiin objective as a loss function, where the actor is conditioned on its individual history of observations. Additionally, we subtract the state value function baseline to reduce the variance:
[(o:) -E atmmraat wart [log x (a()oo))()))))))))))) (s', d d' V* (s
(15)
Equation 15 resembles Equation 7 of the MAA2C algorithm, but instead samples the actions of other agents from -.. In the rest of the paper, the state value and stato-action value functions under policy It will be abbreviated as V and Q respectively. We also replace r + >V (0,) with the equivalent Q(s", a'j : in Equation 115 deviating from typical actor-critic implementations. Additionally, we train a separate network to approximate the state value that is used as baseline in the policy gradient estimation. As a side note, one could avoid the need of training a separate state value network, by computing the baseline as:
V(s+:0,) = Σ Taaiooo
,f
(16)
Foerster et al. (2018) have shown that the baseline described in Equation (6) does not add bias to the policy gradient estimation. Alternatively, we found that training a separate state value results in slightly higher returns. The loss, dcscribed in Eq. (15) above, maximises the Q-values but ignores any miscoordination with the rest of the agents, as it assumees the use of æ+ While this loss still requires centralised training, the actor can be used independently since it is only conditioned on the history of local observations of each agent. We characterise Pareto-AC as an on-policy algorithm, because from the point of view of each agent its local trajectory is on-policy. However, the joint trajectories are off-policy because of the assumption that the other agents -i follow the policy -ł,- The pseudocode of Pareto-AC is presented in Algorithm
The Pareto-AC algorithm is designed to enable agents to learn policies that achieve Pareto-optimality in no-conffict games. We now provide an intuition for why the Pareto-AC algorithm is effective, using the example of a Stag Hunt game (Fig. D In the Stag Hunt game, directly following the policy gradient tends to converge to a sub-optimal equilibrium. This occurs bocause initially, agents have policies that are close uniform. In the case where agent has a uniform policy, the expected returns for the Stag Hunt actions A and B of agent are 2 and 2.5, respectively. This reinforces the selection of action B, making it more likely for agent 1 to choose it. Consequently, agent 2 also tends to prefer action B, resulting in the (B, B) joint action. This example, along with the expected returns, is depicted in Fig. 3a
In contrast, Pareto-AC alters these expectations for any possible policy of the other agents, even if these other policies heavily favour a sub-optimal action. In the Stag Hunt game, the expected rewards of agent 1 for action A and become 4 and 3, respectively, irrespective of the policy T_ that is actually followed by the other agents -i. This is rated in Fig. 3b
6

---

Published in Transactions on Machine Learning Research (10/2023)
Q value of agent actions (a:)
Q(a Q(a
8, a
batch
Q(a: s, a,
8, a
Q(a3)
8,
state (s)
other agent actions (a-+)
(a) The Q network receives imputs the state and the actions of the other agents (concatenated together) and outputs Q value for each of the discrete actions of agent i.
(b) The network architecture allows to compute all the binations of other agent actions in parallel, in a single forward operation. z is the number of joint actions a-; for other agents.
Figure 4: Parcto-AC Q network architecture and parallel computation.
The distinction between the standard policy gradient and Pareto-AC becomes evident when comparing the two scenarios: in the former case, agents learns to prefer action B, while in the latter case, the agents prefer action A, leading to the Pareto-optimal equilibrium. These examples extend beyond simple matrix games and Pareto-AC can guide the agents towards learning policies that achieve Pareto-optimalityy in multi-agent environments.
3.3 Computing - Using a Joint State-Action Value Network
This section addresses the computation of Φł.. The policy tं, of other agents can be approximated at any timestep using joint action value network (also known as a critic):
+ E arg max a-i
Q(s", at, a.:)
(17)
The critic estimates the Q-value the joint actions and can calculate the maximum Q-value the other agents -i from the perspective of agent i.c. max... Q(s² a a",)) The max-opcrator is the core of our approach. Caleulating the maximum Q-value over the possible actions of the other agents translates to assuming that the other agents will follow -łç. Therefore, from the point of view of each agent, the other agents will execute any actions required to reach the Parcto-optimal oquilibrium.
The number of joint actions scales exponentially in the number of agents in the environment, rendering the computation of the Q-values of all joint actions computationally expensive. To allow for fast computation of the Q-value of all joint actions, our algorithm includes two distinct design choices (also seen in Figures 4a and 4b
First, we adopt a strategy that avoids the need for an exponentially increasing critic-network output. We modify the architecture by incorporating the actions of the other agents as inputs (as illustrated in Fig. 4a By doing so, the size of the network scales linearly with the number of agents, effectively mitigating the computational burden (Foerster et al. 2018).
Second, parallelise the computation of Q(s',", a'.). We do so by devising a critie that accepts a batched input that contains the observation concatenated with all the possible a.,. The combinations of the actions a-; is the Cartesian product of the action spaces A-; = Xjzi A which can then be concatenated with the joint observation of all agents. By utilising this input for the critic-network, one is able to compute all the corresponding Q-values in a single forward pass, as depicted in Fig. 4b
The critic network can be trained by following the methodology above. Note that contrast common on- policy actor-critic architectures (e.g., A2C and PPO), Pareto-AC's critic approximates the Q-values instead of the state values. Training the Q-function is done by minimising the TD-error between the selected actions
7

---

Published in Transactions on Machine Learning Research (10/2023)
and the target, which includes the described max-operator:
((),) Bat waa 161 max Q(s aa=)) -a=))- Q(5 at, a(
(18)
a_s
with Q being the target network (updated either with hard or soft updates).
To ensure that the learned Q-value can be used in place of the expected returns Eq. (1),, SARSA-style RRummery Niranjan 1994) updates are used for estimating the Q-value. The use SARSA allows the estimated Q-value for agent be the expected returns under the policy that is currently used by agent i. However, employing one-step SARSA tends to result in overestimation of the returns. Therefore, we adopt N-step SARSA for training the critic. An ablation study with respect to the number of steps is presented in Section 4.5
where the need for employing the N-step computation is highlighted.
Algorithm Pseudocode of Pareto-AC AC algorithm from the point of view of agent
Input: Randomly initialised parameters of the actor Φ; and critic 0g of agent i. Input: The desired number of maximum training steps Naxx Input: A process that interact the environment.
nemepisodes f- 0
while numeepisdes < Max do Create M parallel environments from the environment simulator for 1 ==
do for every environment m in do
Get observations of and o²_; Sample action af (a]lof) and a², -==(a",,0'' Perform the actions and get o411 ott1 , ,(+1
Gather the sequences of all M environments in single batch B
Compute policy ~I,- arg max, Q(s', a a-:) for all
Update the critic using Equation (18
Update the actor using Equation 15
nuMepiaodes + nuMepisodes + .M
Outputs: Trained paramcters the actor Φ; and the critic 0 of agent
3.4 Addressing the Exponential Cost of Calculating m
The architecture proposed in Scction 3.3 allows for efficient computation of Q-values up to a small number of agents. However, the computation becomes prohibitively expensive with larger number of agents, requiring batch size that scales exponentially with the number of agents. Value Function Factorisation (Crites & Guestrin et al. 2001 literature includes many proposals to enable efficient scaling to more
Barto 1998
Q
max ((st,at.a")
Policy Loss
Vi(6*)
Figure 5: Architecture of the PACDCG algorithm. The critic computes the maximum Q-value the joint actions.

---

Published in Transactions on Machine Learning Research (10/2023)
agents. For example, using coordination graphs KKok & Vlassis 2005 Van der Pol & Olichock 2016 one can approximate the max Q-values via a graph-based representation. In this work, we specifically build on top of Deep Coordination Graphs (DCG) (Böhmer et al. 2020), an algorithm that calculates the max Q-values in a Centralised Training Centralised Execution approach.
Equations 15 and 18 only require the maximum Q-value of the joint actions, as well as the Q-values of the specific joint action that is executed at each time step and not the Q-values of all joint actions. DCG assumes that the Q-value of joint action can be factorised using a fully-connected undirected graph, where each node represents an agent that has its own Q-value. Each edge between two nodes represents the pairwisc Q-value between the two agents. Both the individual as well as the joint Q-values are approximated using neural networks. Consider a graph G = (),E), where V is the set of nodes, and & is the set of edges. Assuming that Qi is the individual Q-value of agent 2, and Q2y is the pairwise Q-value of agents and J. following the works of Kok Vlassis (2006); Castellini et al.] (2019), , and more specifically in our case the coordination graph as proposed by |Böhmer ct al. (2020), the joint Q-value can be computed as:
Q(st.a0)= (nllt of) Cisss d))
(19)
i5
DCG is trained using TD-learning to approximate the joint Q-value. As Böhmer et al. 2020 note, DCG is an extension of VDN, with the main difference between the two of them being that DCG also models the pairwise utilities between the agents. If the edges are removed, DCG collapses to VDN. Böhmer et al. (2020) use a message-passing algorithm to estimate the pairwise messages and the individual actions that maximise Q-value over the joint actions. Using DCG as critic we can compute the action that maximise the joint Q-value with complexity [K|[A[[|||+ +NE) (Böhmer et al.) 2020), where k is the number of message passing iterations, |A| the size of the largest single-agent action space, and & the number of edges, in contrast to computing the Q-values of all joint actions with complexity (( A difference between Pareto-AC and PACDCG critics is that in PACDCG the critic estimates that the other agents -i perform the action that maximises the joint Q-value irrespective of the action that agent i performed, while in Pareto-AC the critic estimates that the other agents -i perform the action that maximises the joint Q-value while the action of the agent fixed, ie.. -... variation of Pareto-AC that computes the same values as the PACDCG critic shows worse performance (sce motivation of Parcto-AC in Section 3.1). Additionally, we use a separate neural nelw to approximate centralised stale-value function. Figure 5 presents the architecture of the PACDCG algorithm. Note that PACDCG is restricted to cooperative environments, as direct inheritance of this requirement from the DCG algorithm.
4 Experiments
In this section, we experimentally evaluate Pareto-AC and PACDCG in several multi-agent games and compare them against related baselines. We evaluate whether Pareto-AC and PACDCG achieve superior returns compared to the basclines as well converge to a Pareto-optimal equilibrium.
4.1 Multi-Agent Games
Three common-reward multi-agent matrix games proposed by Claus & Boutilier (1998) the Climbing game with two and three agents and the Penalty game. The payolf matrices of the Climbing game with two agents and the Penalty game are presented in Figure G The Climbing game is a two agents matrix game with three actions per agent. It has in total seven Nash equilibria (Iwo pure-strategy and five mixed-strategy), with the joint action (A, A) being the Pareto-optimal one. We also extend the Climbing game to three agents, with one Parcto-optimal joint action AA The Penalty game is a two agents matrix game with three actions per agent. It has in total five Nash equilibria (three of which are pure- strategy), with Pareto-optimal Nash equilibria being the joint actions (A,C) and (C, A). These matrix games have one or more Pareto-dominated Nash equilibria and one or more Pareto-optimal Nash equilibria.
Matrix Games:
Boulder Push: In the Boulder Push game (illustrated in Figure Sal, two agents and a boulder are situated within 8 8 gord- Boulder Push shares similarities with Box- Mox-Pushing (Seuken & Zilberstein 2007)
9

---

Published in Transactions on Machine Learning Research (10/2023)
A Agent 2
A Agent 2
A
B
C
B
C
A
11
30
0
A
- 100
10
Agent
B
-
30
7
0
Agent
B
2
0
C
6
5
C
10
100
Figure 6: Normal-form of the Climbing (on the left), and the Penalty (on the right) games. The Climbing game has two pure Nash equilibria, where the Pareto-optimal equilibrium is (A,A). The Penalty game has three pure Nash equilibria, where the Pareto-optimal equilibria are the (A,C) and (C,A).
Agent 3
A
B
C
A Agent 2
A Agent 2
Agent 2
B
C
B
C
A
B
Agent 1
A
11
-30
0
-30
0
-30
0
B
-30
0
0
0
0
0
0
0
0
0
6
Figure 7: Normal-form of the Climbing game with three agents. where the Pareto-optimal+ equilibrium is (A, A,
The game has two pure Nash equilibria,
but emphasises penalties for agent miscoordination. Each agent possesses four available actions for cardinal movement directions and observes relative distances to other agents, the boulder, and grid boundaries. Successful boulder movement requires all agents to move in unison, aligning with arrows shown in Fig. Sa while occupying highlighted positions. Agents are rewarded with 0.1 for successfully contributing to boulder movement. Conversely, if agents attempt (and fail) to push the boulder independently, they incur a penalty of -0.1. The optimal joint policy is estimated to yield expected returns of 1.35 for each agent. This calculation comprises a reward of for task completion and an additional 0.35 for participating on average approximately 3.5 times in boulder pushes. Episodes conclude either when the boulder reaches the grid's end after set duration of 50 time steps.
Level-Based Foraging (LBF): In this game, one food item is placed in a 5x5 grid world (Christianos et al. 2020 Papoudakis et al. 2021), as depicted in Figure 8b At the start of each episode, both agents and the food ilem are assigned levels. The agents' primary objective is to forage the food item. To do so, group of agents can successfully forage the food item only if the sum of their levels equal to or greater than the level of the food item. Each agent's observation includes their level, as well as the levels and relative distances other agents and the food item. Agents can move the four cardinal directions, attempt to forage the food take no action. Successful coordination and foraging yield reward of +1 for all participating agents, while failed attempts result in penalty of -0.6 for each agent. Episodes end when either the food item is successfully gathered or after 25 time steps. The LBF task has two versions: one with two agents and one with three agents. In the two-agent. LBF, both agents must simultaneously forage the food item. Tn the threc-agent LBF, the food item's level is randomly initialised, meaning it may require one, two, or all three agents to forage it at once.
4.2 Experiment Details
We compare the average evaluation returns achieved by Pareto-AC AC against the evaluation returns achieved by seven MARL algorithms: MAPPO (Yu et al. 2021). MAA2C, VDN (Sunchag et al.) 2018). QMIX (Rashid
et al. 2018), QTRAN (Son et al. 2019), QPLEX (Wang et al. 2021), and Friends Q-Learning (Friends-
QL) Littman 2001). Table summarises all evaluated algorithms and their core properties.
Friends-66 QL was proposed a tabular form by Littman (2001). In this work, the architecture of Figs. and 4b was used to apply it in the deep learning setting. With Friends-QUP BLonds-L,, each agent consists of neural network that approximates the joint Q-value. During execution, each agent selects its action assuming that
10

---

Published in Transactions on Machine Learning Research (10/2023)
(a) Boulder Push environment.
(b) Level-Baser Foraging environment.
Figure 8: Boulder Push and the Level-Based Foraging environments. In both environments, the agents are penalised if they individually try to complete the task without cooperating with the other agent.
Table 1: Overview of the evaluated algorithms.
Value Network
On-/Off- Policy
Environment Settings
Pareto-AC (Ours)
Joint-Action
On
No-Conflict
PACDCG (Ours)
Joint- Deott-Decomposttion
On
Cooperative
Friends-QI.
Joint-Action
Off
No-Conflict
MAA2C
State Value
On
All
MAPPO
State Value
On
All
VDN
Joint-Decomposition
Off
Cooperative
QMIX
Joint-Decomposition
Off
Cooperative
QTRAN
Joint-Decomposition
Off
Cooperative
QPLEX
Joint-Decompositionn Off
Cooperative
other agents will choose the action that maximises the joint Q-value. Friends-QL is the Temporal Difference equivalent of Pareto-AC, where both algorithms assume that the other agents will follow Tí, with the different being that that Pareto-AC uses actor-critic method to learn the policy while Friends-QI. uses Q-Learning.
All on-policy algorithms use N-step returns to train their critics. In the case of Pareto-AC, and PACDOG, the use of N-step returns can render the Q-value estimation to be under different policy from x+ for the first steps. While this not theorctically justified, we found it a necessary modification to reduce overestimation as we experimentally show in Section 4.5
Gradient updates are performed at the end of each episode. Value-based algorithms (VDN, QMIX, QTRAN, QPLEX, and Friends-QL) and the gradient updates are performed by uniformly sampling batch of 32 episodes. Actor-critic algo- rithmss (MAA2C, MAPPO, Pareto-AC, PACDCG) use ten parallel processes to break the correlation between consecutive samples, and the gradient updates are performed using batch of the ten aggregated episodes. Following the work of Papoudakis et al. (2021). we retain the same number of updates across all algorithms, meaning that on-policy algorithms observe 10 times more environment timesteps compared to off-policy.
experience replay to break the correlation between consecutive samples,
All neural networks consist of two fully connected layers in fully-observable environments (matrix games and LBF), while the first layer of the actor is GRU in the Boulder Push environment. The parameters of all networks are optimised using the Adam optimiser (Kingma & Ba 2015). There is no parameter sharing among the agents. Pareto-AC and PACDCG were implemented based on the EPyMARL codebase [Papoudakis et al. 2021) The implementation PACDCG's critic was based on the official implementation of DCG Böhneer et al. 2020).
We performed a hyperparameter search to systematically examine multiple configurations for the training process for both the baseline algorithms and Parelo-AC. Our approach ensured fairness by maintaining
11

---

Published in Transactions on Machine Learning Research (10/2023)
Climbing Game
Penalty Game
Climbing Game (3 Agents)
22.
Evaluation Returns
Evaluation Returns
Evaluation Returns
204
30
1WM
5000
26:00
1900
4000
500X
2000
Time Steps
Time Steps
Time Steps
Boulder Push
Level-Based Foraging Agents)
Level-Based Foraging Agents)
Evalluate Avallaatio Returns
Evaluation Returns
04
Evaluation Returns
2.0
04
-62
Time Steps
181
Time Steps
200
Time Steps
Max Return
Pareto-AC (DCG)
MAA2C
VDN QMIX
QTRAN
Pareto-AC
Friends-QL
MAPPO
QPLEX
Figure 9: Average episodic evaluation returns and 95% confidence interval over 5 seeds of Pareto-AC and the evaluated baselines six multi-agent environments.
roughly equal number of search configurations for all algorithms under consideration. A detailed description of the hyperparaneters can be found in the appendix.
4.3 Average Evaluation Returns
Figure presents the average evaluation returns over five different sceds, which are achieved by Pareto-AC and four evaluated baselines in the aforementioned environments. Figure I0 illustrates the same runs by summarising the maximum performance achieved by each algorithm-environnen pair.
Matrix Games: Pareto-AC is the only method that converges to the Parcto-optimal equilibria in all games.. Briends-QL converges to the Pareto-optimal equilibrium in the Climbing games with both two and three agents, but it does not converge in the Penalty game, any the equilibria. The reason behind this can be attributed to the fact that the Penalty game has two Pareto-optimal equilibria. In Friends-QU BL the agents do not have an explicit mechanism for deciding their joint action and are solely choose their actions based on the fact that the other agent will choose the action that maximise the joint Q-values. By looking into the individual runs and evaluations of friends-LL in the Penalty game, we observe that in all evaluation points the agents either select one of the Pareto-optimal equilibria or choose the joint actions (A, A) or C) which result in -100 penalty. This is a direct result of miscoordination between the agents selecting different Pareto-optimal equilibria. Pareto-AC does not have this problem, as during the training process if agent 1 assigns a higher probability say to action A (e.g. 0.51), agent 2 will be strongly reinforced to converge to the respective action (C in this case) and avoid the aeavily-pnnaiieed A action (and the opposite direction also holds). MAA2C and MAPPO both converge to the Pareto-opting optimal equilibrium in the Penalty game. However, both of them converge a sub-optimal joint action in the two Climbing games. PACDCG and QPLEX converge to the Parelo-optimal equilibria in the Climbing game with two agents, and the Penalty game. PACDCG converges to a Pareto-dominated equilibrium in the Climbing game with three agents. We believe that this due to the graph factorisation. The DCG critic only models pairwise value functions, and is not able represent values in environments where the reward needs the cooperation of more than two agents.
12

---

Published in Transactions on Machine Learning Research (10/2023)
Climbing (2 agents)
Penalty
Climbing agents]
Pareto-AC
Poreto AC
Pareto-AC
PACDCG
PACDOG
PACDCG
FriendsOOL.
Friends-QL.
Friends-QL
MAA2C
MAA2C
MAAZC
МАPРO
MAPPO
MAPPO
QMIX
QMIX
QMIX
QTRAN
OTRAN
QPLEX
QPLEX
QPLEX
Returns
Maximum
Boulder Push
Level-based Foraging (2 agents)
Level-based Foraging (3 agents)
Parato-AC
Porcto AC
Pareto-AC
PACDCG
PACDOG
PACDCG
Friends-QL
Friends-OL
Friends-QL
MAPPO
MAPPO
MAPPO
QMXX
QMIX
QMIX
OTRAN
OTRAN
OPLEX
QPLEX
OPLEX
1.0
Maximum Returns
Maximum Retums
Maximum Returns
Figure 10: Box plot with maximum evaluation returns for Pareto-AC and the evaluated baselines six multi-agent environments. The box plot draws a box from the first to the third quartile, excluding outliers and includes line that goes through the box at the median. Each individual dot signifies the maximum returns achieved by single run (with distinct seed).
Boulder Push: Parelo-AC converges to higher returns compared to all the other baselines. During the first half of the training, Pareto-AC is receiving negative returns which is evidence to support that it insists on exploring promising joint actions even if they are initially penalised. VDN and QMIX also learn to complete the task, however, not as successfully as Pareto-AC. This indicates that while the agents learn to coordinate in some case, there are time steps where the agents miscoordinate and this results in getting penalised. Finally, PACDCG achieves returns that are slightly higher than zero, which indicates that manages successfully solve the task, but miscoordination between the agents occurs frequently.
Level-Based Foraging: Because of the large penalty in this environment, Pareto-AC and PACDCG are the only algorithms that achieve returns significantly higher than zero in the LBF task with two agents. We hypothesise that this a direct outcome of the proposed Pareto-AC objective (Eq. (10)). ) the LBF task with three agents, besides Pareto-AC and PACDCG, Friends- QL and MAPPO also manages achieve re- turn higher than zero. Parcto-AC achieves returns close which the optimal value, while PACDCG, and MAPPO achieve returns close to 0.6 indicating that once the food has level that requires the cooperation of all three agents they unable to forage it.
In both LBF and BPUSH tasks, we observe that Parcto-AC significantly outperforms Friends-QL. with respect to the achieved returns. This may be caused by the optimal joint policy not being unique, similarly to the Penalty game. Additionally, variants achieve lower returns and are less stable than actor-critic algorithms varioty of environments including grid-worlds. As result, the differences in the underlying algorithms may be a reason we observe Friends-QI. to perform worse than Pareto-AC in terms of achieved returns.
has also been observed (Papoudakis et al., 2021 that Q-learning
13

---

Published in Transactions on Machine Learning Research (10/2023)
so_ many saanybaanllnng Cannellnn
1c3s5z
20
18
18
Evaluation Returns
16
Evaluation Returns
16
14
12
12
10
10
Time Steps
1c6
Time Steps
1c6
PACDCG
MAPPO
QMIX
QPLEX
MAA2C
VDN
QTRAN
Figure 11: Average episodic evaluation returns and the 95% confidence interval of PACDCG and the evaluated baselines in two SMAC lasks.
4.4 Evaluating PACDCG in Environments with Many Agents
The effectiveness of computing - using the DCG critic has also been evaluated in the multi-agent games of Section 4.1 The results presented in Figs. g and T0 showed that PACDCG learned in many environments that other algorithms did not. PACDCG converged to the optimal equílibrium in the Climbing (2 agents) and Penalty games and was the second- best algorithm after Pareto-AC in LBF. Therefore, we conclude that the DCG critic can approximate, but outperform the computation of Eq. (18
To showcase that PACDCG can be used even in tasks with many agents, where Pareto-AC cannot, also evaluate in two Starcraft. Multi-Agent Challenge (SMAC) tasks. The two lasks, vo_many, vo_many_baneelll baneling and 1c3s5z, contain seven and nine agents respectively.
In Fig. we present the returns over the training for PACDCG and baselines from Section 4.3 except Friends- QL which similarly to Pareto-AC cannot scale to several agents, due to the exponential increase of evaluation that are required for computing the Q-values. The SMAC tasks shown here were selected for their number of agents, and do not exhibit the high-risk-hiig--rwaan property, and such, other algorithms also solve them. However, this experiment shows the feasibility of computing an approximation of π using value function factorisation algorithms.
That said, The problem arises when only a few joint actions lead to successful coordination, creating a situation where it becomes difficult to discover these actions within a reasonable number of episodes. As an example, a simple 20 x 20 grid-world like LBF (Fig. (bb) with 10 agents could have many 1026 states. If each state has a joint action space of size 10 exploring each joint state-action would be completely infeasible. Therefore, the experiments conducted on many agents were limited to environments in which informative gradient exists.
settings for large number of agents encounter the problem of exploration.
4.5 Addressing Overestimation and the Effect of N-step Returns
In this section, we explore the use of N-step returns in training the critics the Pareto-AC algorithm. The critics are responsible for approximating the expected returns for cach agent. By incorporating N-stop SARSA from the perspective of agent and Q-learning from the perspective of agents -i, we aim to mitigate the overestimation of the expected returns. With N-step returns, Eq. (18) becomes:
14

---

Published in Transactions on Machine Learning Research (10/2023)
Level-Based Based Foraging 12 Agents)
Level-bosed Foraging 12 agents)
Level-Besed Foraging (2 Agents)
Max Return
1-step
1.0
1-Step
1-step
16
2-step
Evalucttion Raturs
2-step
5-stap
0.5
10-step
S Stop
2-step
Mean Q-velues
0.0
10 stop
0.4
0.2
0.0
-02
ID-step
-04
-04
0.6
Maximum
Time Steps
Set
Time Steps
Jur
(a) Learning curves.
(b) Maximum achieved returns.
(c) Mean Q-values during training.
Figure 12: Pareto-AC on Level-based Foraging for different values of N.
[(0.) = Bugiol "uuia nx [1r, + tmm ... x - ty max Q a
s+N a-_)) Q(ss Q(s".at, a(, (20)
rewards sampled using
approx. (mumL, Q values
The use of N-step returns for training the critic provides mechanism to balance the returns as sampled from the environment which follows n, and the approximated returns of at. A large N value reduces the critic to one that simply learns the Q g while when N it approximates the action value function Q" proposed in Eq. (18.. N can be treated as hyperparameter.
To evaluate the effectiveness of different values, we conducted experiments with Pareto-AC and N values 1, 2, 5, and on the LBF environment with two agents. The average evaluation returns over the training are presented in Figure I2a] while the maximum evaluation returns over the five seeds are shown in Fig. [2b Figure [2c presents the mean Q-values during the course of the training, and we note that the maximum possible discounted returns that can be achicved are in the range close 0.9 1.0. The results indicate that:
N achieves significantly lower returns, because of the overestimated Q-values. The overestination of the Q-values is clear from Fig. [2c in which the 1-step line is significantly higher the early to middle stages of the training than the other N values, even if it does not achieve returns close to that range (sce respective returns in Fig. 12a The overestimation also causes lower converged returns, which is seen in
Fig. 12b
2,5, 10 do not overestimate their returns and the Q-values (Fig. 12c closely follow the returns achieved (Fig, 12a). Both N values (and presumably any values in that range) converge to solving the environment with returns close to 1.0.
We conclude that there an optimal range of values that not too narrow and can be easily found with hyperparameter search (in the case of Level-based Foraging is values around 5). N values this range prevent the overestimation of the Q-values while retaining the advantages proposed in Section 3.2
4.6 Evaluation on No-Conflict Matrix Games
The multi-agent games described above are fully cooperative since the reward is common across all agents. However, Pareto-AC works in the general no-conflict case, a superset the cooperative games. We evaluate our algorithm in the set of all structurally distinct strictly ordinal 2 x 2 no-conflict games (Albrecht & Ramamoorthy 2012 Rapoport 1966). We train agents with Parcto-AC, Friends-QL,, MAA2C, and IQL for
Note that does not collapse Pareto-AC A2C
still optimises the modified objective Eq. 15
15

---

Published in Transactions on Machine Learning Research (10/2023)
Table 2: Categories of MARL environments.
Reward Structure
Example Environments
Comments
General Sum Games
MPE, LBF
Encompusses all subeateguries duscribed below.
No-Conflict
Stag Humt, Climbing, SMAC
Strong preference for Pareto-optimal equilibria (see Section 2 Subcategory of no-conflict games, widely explored in the literature. Pareto optimality has limited significance. Pareto optimality nuanced but relevant.
Common-Rewwad
Climbing, Ponalty, SMAC, GRF RPS. Chess, Predator-Pree Prey
Zero-Sum/ / Competitive
Social Dilemma
Prisoner's Dilemma, Harvesting
five seeds until convergence to one of the joint actions. In those runs, Pareto-AC AC and Friends-QU. QL solve all 21 games (on all five scods) by converging to the Parcto-optimal equilibrium, while MAA2C and IQL do not consistently solve three of these games in all five tested seeds. We note that 15 of the 21 games only have one equilibrium, so it is not surprising that every algorithm solved them. The three games that were not solved by other algorithms can be seen in Fig. 13 and exhibit similar structure to the Stag Hunt (Fig, [ Note the inclusion of only simpler baselines, since QMIX, VDN, QTRAN and QPLEX assume common-reward games and do not apply to the general no-conflict setting.
A
B
A (4, 4)
B
A
B
[4 4)
(1,3)
(1,2)
A
4,
4)
(1,2)
(3,
22,2)
(3, 1)
(2, 2)
B
(2,
(3,
3)
Figure 13: Normal-form of the games not solved by MAA2C and IQL. The top-left game is structurally
identical to the Stag Hunt (Fig. ! and the others exhibit similar structure. All games have two pure Nash equilibria, one that is Pareto-dominated and one that is Pareto-optimal",
5 Related Work on Multi-Agent Reinforcement Learning
No-conflict games (Rapoport 1966 Albrecht & Ramamoorthy 2012 represent a significant class of multi- agent games. In Section 2 we give a more detailed definition of this game class. A subset of no-conflict games, common-reward games (also referred to as cooperative games) have been studied extensively in the
deep MARL community (o.g. Rashid ct al.) 2018 Foerster ct al. 2018 Sunchag et al., 2018 Son et al.
2019 Wang et al. 2021 Parelo-AC naturally applies to this subclass of games, but also to the more general no-conflict setting in which all agents strongly prefer the Pareto-optimal equilibria.
The concept of Parcto equilibrium has been extensively examined in various contexts (e.g. Pardalos et al., 2008 Albrecht et al.] 2023). In social dilemma games, such as the Prisoner's Dilemma, achieving Parelo efficiency is desirable outcome, although it often falls short of addressing the complete issue of finding the best joint policy Similarly, in other general-sum games, the notion of Pareto efficiency can offer valuable insights. However, in the context of zero-sum games, Pareto optimality is not meaningful, as all joint actions are Pareto optimal. We summarise the main categories of MARL environments based on their reward structure in Table 2
In this work, we focused on cooperative and no-conflict games, and specifically environments that contain high- Nash equilibria. Below, we discuss closely related research topics to Pareto-AC, well as algorithms that address the equilibrium selection problem and algorithms that fall under the CTDE paradigm.
5.1 Equilibrium Selection
Several works have been proposed to address the equilibrium selection problem that mainly focus on accu- rately learning the Q-value of the joint actions. Littman (2001) proposes two different approaches; one for
4 An example is the classic Prisoner's Dilemma game, where (C, C) yiclds -1), (D, C) and (C, D) yield (0, -3) and (-3, 0). respectively, and finally (D, D) yields (-2, -2), the joint action (D, D) represents the only Nash equilibrium but is the sole joint action that does meet the Pareto efficiency criterion.
16

---

Published in Transactions on Machine Learning Research (10/2023)
games where the other agents are considered friends (Friends-QL), and one for games where the other agents are considered foes (Foe Q-learning). Assuming a game with two agents, in Friends-QU QL each agent maintains a table of Q-values for all joint actions, which are updated using the following rule:
Qr(s'.ai.00 - a1-a)Q((s* .i. + aarr ty max Q1(st+1
al a2 , a2.)
(21)
where is the learning rate. From the perspective of each agent i, Friends-QL assumes that the other agent -i will always select the action that maximises the joint Q-values of agent i. Claus & Boutilier (1998) evaluate independent and joint-action learning in cooperative games with several Nash equilibria, such as the Penalty and the Climbing game. Wang & Sandholm (2002) propose OAL, a joint-action learning algorithm that guarantees convergence to the Parelo-optimmal equilibrium. In contrast to Pareto-AC, OAL needs to learn a model of the environment's 's transition and reward function. More recent works focus on learning the Q-values of the joint actions, by mixing the Q-values for the actions of cach individual agent (Sunchag al., 2018 Rashid et al.) 2018 Son el al.] 2019), which however are restricted by the representa aliin capacity of the mixing algorithm. Another way of computing the Q-values of the joint actions is based on coordination graphs (e.g. KKok & Vlassis 2006] Castellini et al. 2019 Böhmer et al. 2020 Wang et al. 2022), where each agent is represented by a node, while the pairwise utility between two agents is represented by an edge, and by using the message-passing algorithm in the graph the Q-value of each joint action can be computed.
Leniency in MARL (Panait et al. 2006) trains agents in a way that they are lenient to their teammates by focusing the positive outcomes of coordination. Lenient-DQN (Palmer et al.) 2018) extends this idea to the deep learning setting by mapping state-action pairs stored in an experience replay to a decaying temperature (Palmer et al. 2018). Similarly, Hysteretic Q-Learning (Matignon et al. 2007) uses two learning rale values in order to reduce the magnitude of negative Q-value updales. Lenient Multi-Agent Reinforcement Learning 2 (LMRL2), introduced by Wei & Luke (2016), employs the mean temperature of an agent's 's present state and a Boltzmann action selection method to calculate the weight of cach action, thereby prioritising exploration in states that have been visited less frequently. All these algorithms attempt to introduce oplimism (e.g. Claus & Boutilier 1998 Lauer & Riedmiller 2000) in multi-agent interaction. Pareto-AC is also optimistic but does so by modifying the learning objective, and is shown to be effective even in POSGs with high-dimensionalltyy sparse rewards, and significant penalties.
5.2 Centralised Training Decentralised Execution
Centralised Training Decentralised Execution (CTDE) is a class of algorithms that mitigate the uncortainty each agent has about the policies of the other agents by allowing information (such as local observations and actions) be shared during training. During execution, each agent selects their actions a decentralised manner, only based on their own information (observation-action history). Two large classes of CTDE are the Centralised Policy Gradient Algorithms, and the Value Factorisation Algorithms. Centralised Policy Gradient Algorithms are actor-critic methods that consist of a decentralised actor and a centralised critic. During training, the critic is trained centralised to approximate the joint state (V-value) or joint state-action (Q-value) value function conditioned on the global trajectory of all agents. During execution, the decen- tralised actor of each agent selects its actions only based on its local trajectory. Some notable centralised policy gradient algorithms are MADDPG (Lowe et al.) 2017), COMA (Foerster et al. 2018). MAA2C (Pa- poudakis et al., p and MAPPO (Yu al. 2021). Value Function Factorisation Kok & Vlassis (2005) algorithms are limited to cooperative environments, that factorise the global scalar reward into individual utilities for each agent. Such algorithms in the deep learning setting include VDN (Sunehag et al. 2018) and QMIX (Rashid et al. 2018). Both of these approaches require the monotonicity constraint, which means that the argmax of the joint Q-value is the same as the joint action that is generated if we perform the argmax operator in the individual Q-values of each agent. There are several algorithm variations in both categorics that extend that focus on relaxing this constrain to be able to approximate a broader class of joint Q Q-values, such as QTRAN (Son et al. 2019),, and QPLEX (Wang et al. 2021), which however do not always yield higher returns compared to the simpler VDN, and QMIX algorithms.
17

---

Published in Transactions on Machine Learning Research (10/2023)
6 Conclusion
We proposed Pareto-AC, an actor-critic MARL algorithm designed to converge to Pareto-optinal Nash equilibria in no-conflict multi-agent games, The algorithmic choices behind Pareto-AC are based on the assumption that in no-conflict games, each agent can assume that the other agents will choose the action that will lead to the Pareto-optimal equilibrium. While the community has developed approaches to solve matrix games with risk-averse equilibria, this work exlends these approaches to the deep learning setting and environments with high dimensionality. Our results showed that Pareto-AC is able to achieve higher returns, and converges more often to the Pareto-optimal oquilibrium, compared to several state-of-the-art MARL algorithms,, such as MAPPO and QPLEX. Pareto-AC also outperforms deep learning implementation of the Friends-QL. algorithm since it learns to converge to one of the multiple equivalent equilibria using its policy network. Additionally, to address the computational bottleneck that is raised by the exponentially increasing number of Q-values, we proposed PACDCG as a scalable approximation of Parcto-AC that uses the DCG algorithm for its critic. Two main directions future research emanate from this work. The first direction the theoretical understanding of Pareto-AC, and under which requirements we can guarantee that it will converge to Nash equilibrium even a Parcto optimal Nash equilibrium. Second, we aim to explore extensions beyond no-conflict games, replacing the max operator with min-max based approaches (e.g. Littman 2001 for zero-sum games.
References
Stefano V. Albrecht and Subramanian Ramamoorthy. Comparative evaluation of multi-agent learning algo- rithms in a diverse set of ad hoc team problems. In Proceedings of the 11th International Conference Aulonomous Agents and Mulliagent Syslems- Volume 1, pp. 349 356, 2012.
Stefano V. Albrecht and Peter Stone. Autonomous agents modelling other agents: A comprehensive survey and open problems, 2018. ISSN 00043702.
Stefano V. Albrecht, Filippos Christianos, and Lukas Schäfer. Mulli-Agent Reinforeement Learning: Foun- dations and Modern Approaches. MIT Press, 2023. URL https://www https://www.marl-bbbtt waw.-book.. com
Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. In International Con-
ference on Machine Learning, pp. 980 991. PMLR, 2020.
Jacopo Castellini, Frans A. Olichock, Rahul Savani, and Shimon Whiteson. The representational capacity of action-value networks for multi-agent reinforcement learning. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '19, pp. 1862-1864, Richland, SC, 2019. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 9781 450363099.
Filippos Christianos, Lukas Schäfer, and Stefano V. Albrecht. Shared experience actor-critic for multi- agent reinforcement learning. In Advances in Neural Information Processing Syslems, volume 33, pp. 10707-10717. Curran Associates, Inc., 2020. URL fLlp//9BrccaaaBBEBBeccccchcchtdt Paper. Paw.eeeeeeppppp.... pdf
Filippos Christianos, Georgios Papoudakis, Arrasy Rahman, and Stefano V. Albrecht. Scaling multi-agent reinforcement learning with selective parameter sharing. In International Conference Machine Learning (ICML), 2021.
Caroline Claus and Craig Boutilier. The dynamics of reinforcement learning in cooperative multiagent systems. AAAT Conference on Artificial Intelligence, 1998.
Robert H. Crites and Andrew G. Barto. Elevator group control using multiple reinforcement learning agents. Mach. Learn., 23(2-3):235-26,, 1998. doi: 10.1023/A (:023///100077517744497 URL https:://oi.org:: http://o.....//.....1/ 1023/ 4:1007518724497
Thomas Degris, Martha White, and Richard S Sutton. Off-policy actor-critic. In International Conference on Machine Learning, 2012.
18

---

Published in Transactions on Machine Learning Research (10/2023)
Jakob N. Foerster, Yannis M. Assael, Nando de Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement. learning. In Proceedings of the 30th International Conference on Newral Information Processing Systems, NIPS'1 pp. 2145 2153. Curran Associates Inc., 2016. ISBN 118-1-5108-3881---
Jakob N. Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Coun- terfactual multi-agent policy gradients. In Phirly-Second AATT Conference on Artificial Intelligence, 2018.
URL https:/ /www://wwww../ aaai. .rgg wwrg//cc/inccee php/
Carlos Guestrin, Daphne Koller, and Ronald Parr. Multiagent planning with factored mdps. In Thomas G. Dietterich, Suzanna Becker, and Zoubin Ghahramani (eds.), Advances in Neural Information Process- ing Systems 14 (Neural Information Processing Systems: Natural and Synthetic, NIPS 2001, December 3-8, 2001, Vancouver, British Columbia, Canadaj, pp. 1523 1530. MIT Press, 2001. URL https://
Abstrcctt.btttttt..cc .html
Eric A Hansen, Daniel S Bernstein, and Shlomo Zilberstein. Dynamic programming for partially observable stochastic games. In AAAL, volume 4, pp. 709-715, 2004.
John C Harsanyi and Reinhard Selten. A general theory of equilibrium selection in games. MIT Press Books, 1, 1988.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 2015.
Jelle R. Kok and Nikos Vlassis. Using the max-plus algorithm for multiagent decision making in coordination graphs. In Katja Verbeeck, Karl Tuyls, Ann Nowé, Bernard Manderick, and Bart Kuijpers (eds.), BNAIC 2005 Proceedings of the Sevenleenth Belgium, October 17-18, 2005, pp. 359-360 Koninklijke Vlaamse Academie van Belie voor Wetenschappen en Kunsten, 2005.
Conference Arlificial Intelligence, Brussels,
Jelle R Kok and Nikos Vlassis. Collaborative multiagent reinforcement learning by payoff propagation. Journal of Machine Learning Research, 7:1789 1828, 2006.
Martin Lauer and Martin A. Riedmiller. An algorithm for distributed reinforcement learning in coopera- tive multi-agent systems. Tn Proceedings of the Seventeenth International Conference on Machine Learn- ing, ICML '00, pp. 535-542, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc ISBN 1558607072.
Michael L. Littman. Friend-or-foe gelaarning in generalsum games. In International Conference Machine Learning, Williamstown, pp. 322-328, 2001.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperative-oompetttiee environments. In Advances in Newral Information Processing Systems, volume 30, pp. 6379-6399 2017. URL
Xueguang Lyu, Andrea Baisero, Yuchen Xiao, Brett Daley, and Christopher Amato. On centralized critics in multi-agent reinforcement learning. J. Artif. Int. Res., 77, may 2023. ISSN 1076-9757. doi: 10.1613/
jair.1.14388 URL hattps://di..rggee
1111/ jair. 14386
Laetitia Matignon, Guillaume J. Laurent, and Nadine Le Fort-Piat. Hysteretic q-learning; an algorithm for decentralized reinforcement learning in cooperative multi-agent teams. In 2007 BEEE/SS) International Conference on Intelligent Robots and Systems, pp. 64-69, 2007. doi: 10.1109/TRO5 207.520000733900005
Volodymyyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In In- ternational Conference on Machine Learning, pp. 1928-1937. PMLR, 2016. URL http:://tpooo attp://proceedings. mlr. www.press//4//miiaafe6 html ISSN: 1938-7228.
19

---

Published in Transactions on Machine Learning Research (10/2023)
Gregory Palmer, Karl Tuyls, Daan Bloembergen, and Rahul Savani. Lenient multi-agent deep reinforcement learning. In Flisabeth André, Sven Koenig, Mehdi Dastani, and Gita Sukthankar (eds.), Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018, pp. 443-451. International Foundation for Autonomous Agents and Multiagent Systems Richland, SC, USA / ACM, 2018. URL http::/dll acm. wttp://iaatiinnncnnni.aaaaaaeeee con
Liviu Panail, Keith Sullivan, and Sean Luke. Lenient learners in cooperalive multiagent systems. In Hideyuki Nakashima, Michael P. Wellman, Gerhard Weiss, and Peter Stone (eds.), 5th International Joint Confer- ence on Autonomous Agents and Multiagent Systems (AAMAS 2006), Hakodate, Japan, May 8-12, 2006, pp. 801 803. ACM, 2006. doi: 001144/111663..111 1160776
URL https: http:://doi.org/1// 1ttg/10.114555 1.0.1111/116063.
Georgios Papoudakis, Filippos Christianos, Lukas Schäfer, and Stefano V Albrecht. Benchmarking multi- agent deep reinforcement. learning algorithms in cooperative tasks. In Thirby-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2021. URL httpt:: https://openrevvee..neo
Forum?2d=cIrPX--n...
Panos M Pardalos, Athanasios Migdalas, and Leonidas Pitsoulis. Pareto optimality, game theory and equi- libria, volume 17. Springer Science & Business Media, 2008.
Anatol Rapoport A laxonomy of 2x 2 games. General systems, 11:203 214, 1966.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning. Tn International Conference on Machine Learning, pp. 4295-4304 PMLR, 2018. URL httph::t///proeeedingg ISSN: 2640-3498.
mlr. wtt.prres//80/rashd11.. html
Gavin A Rummory and Mahcsan Niranjan. On-line Q-learning using connectionist systems, volume 37. University of Cambridge, Department of Engineering Cambridge, UK, 1994.
Sven Seuken and Shlomo Zilberstein. Improved memory-bounded dynamic programming for decentralized pomdps. In Proceedings of the Twenty- Third Conference on Uncertainty in Artificial Intelligence, UA107, pp. 344-351, Arlington, Virginia, USA, 2007. AUAT Press. ISBN 0974903930.
Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Farl Hostallero, and Yung Yi. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In International conference on machine learning, pp. 3887-5896. PMLR, 2019.
Peter Sunchag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnocki, Vinicius Zambaldi, Max Jader- berg, Marc Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, and Thore Graepel. Value-decomposition networks for cooperative multi-agent learning based on team reward. In Proceedings of the 17th Interna- tional Conference on Autonomous Agents and MultiAgent Systems, AAMAS '18, pp. 2085-2087. Interna- tional Foundation for Autonomous Agents and Multiagent Systems, 2018.
Elise Van der Pol and Frans A Oliehoek. Coordinated deep reinforcement learners for traffic light control. Proceedings of learning, inference and control of multi-agent systems (at NIPS 2016), 8:21-38, 2016.
Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang, Qplex: Duplex dueling multi-agent
q-lcarning. In International Conference on Learning Representations, 2021.
Rundong Wang, Xu He, Runsheng Yu, Wei Qiu, Bo An, and Zinovi Rabinovich. Learning efficient multi- agent communication: An information bottleneck approach. In International Conference on Machine Learning, pp. 9908 1918.999...11111 PMLR, 2020.
Tonghan Wang, Liang Zeng, Weijun Dong, Qianlan Yang, Yang Yu, and Chongjie Zhang. Context-aware sparse deep coordination graphs. International Conference on Learning Representations, 2022.
Xiaofeng Wang and Tuomas Sandholm. Reinforcement learning to play an optimal nash equilibrium in team markov games. Advonces in newral information processing systems, 15, 2002.
20

---

Published in Transactions on Machine Learning Research (10/2023)
Ermo Wei and Sean Luke. Lenient learning in Independent-leameee stochasicc cooperative games. Journal of html
Machine Learning Research, 17(84):1-422 2016. URL http:::/jjall..rgg/pppprrrseseet
Ronald J. Williams. Simple Statistical Gradient- Following Algorithms for Connectionist Reinforcement
Learning. Machine Learning, 8(3-4)2229225) 256, 1992. ISSN 0885-6125. doi: 10.1007/bf009990000
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness PPO in cooperative, multi-agent games. arXiv preprint Xtv: 01955, 2021.
21

---

Published in Transactions on Machine Learning Research (10/2023)
A Implementation and Hyperparameter Details
Throughout the hyperparameter scarch, we systematically examined multiple configurations for the training process for both the baseline algorithms and Parelo-AC. Our approach ensured fairness by maintaining a roughly equal number of search configurations for all algorithms under consideration. This included testing hidden dimensions of 64 and 128, learning rates of 0.0003 and 0.0005, considering both Fully Connected (FC) and GRU network architectures, and experimenting with initial entropy coefficients of 0.1, 0.8, and 20, well as final entropy coelficients of 0.001, 0.01, and 0.02 (entropy only applies to PG algorithms). To select the hyperparameter configurations used to generate the results (Tables 3 to 5) that were presented in Section 4 trained all hyperparrameter configurations for five different seeds for each algorithm. Then we chose the configuration that achieves the maximum evaluation return averaged over all evaluation time steps and seeds.
The norm of the gradient is clipped to 10 in all algorithms. the actor-critic methods, we subtract the policy's entropy, multiplied by an entropy coefficient, from the policy gradient loss to ensure sufficient exploration. We found it benefieial to start with large entropy coefficient and gradually reduce it to smaller value throughout training. We set initial entropy values to 1.5 and 0.8, and final entropy coefficient values to 0.01, 0.02, and 0.03.
Table 3: Hyperparameters for Pareto-AC in all environments.
Climbing
Penalty
Climbing 2 Ag.
Boulder Push
LBF 2 Ag.
LBF Ag.
hidden dimension
64
64
64
128
128
128
initial entropy coeff
4
20
0.8
0.8
0.8
final entropy coeff
0.1
0.1
0.1
0.01
0.02
0.02
entropy anneal pere
80%
80%
80%
100%
80%
100%
learning rate network type
0.0003
0.0003
0.0003
0.0005
0.0003
0.0003
FC
FC
FC
GRU
FC
FC
Table 4: Hyperparameters for PACDCG in all environments.
Climbing
Penalty
Climbing 2 Ag.
Boulder Push
LBF 2 Ag.
LBF 3 Ag.
hidden dimension
64
64
64
128
64
64
initial entropy coeff
4
20
0.8
1.5
1.5
final entropy coeff
0.1
0.1
0.02
0.01
0.03
0.02
entropy anneal pere
80%
80%
80%
100%
100%
100%
learning rate network type
0.0003
0.0003
0.0003
0.0005
0.0003
0.0003
FC
FC
FC
GRU
FC
FC
Table 5: Hyperparameters for PACDCG in the SMAC tasks.
many baneling
1c3s5z
hidden dimension
64
64
entropy coelf
0.01
0.01
learning rate
0.0005
0.0003
network type
FC
FC
22


Reviews:
[{"review_id": "B1rn35eePx", "reviewer": "Reviewer_q1VR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nAlmost everything in this paper makes sense: the design decisions, the choice of problem domains, the experiments, and the claims made. The paper is mostly easy to follow and makes a reasonable contribution in the context of no-conflict games. I absolutely love the intuition provided in the first paragraph of page 2. Well done! \n\n**Weaknesses**\n\nThe paper boils down to a comparison of Actor-Critic algorithms and Q-Learning algorithms in the context of no-conflict games through PAC and Friends-QL. While this can be perceived as a modest contribution, I appreciate that the comparison was nicely done. However, I still don't fully understand why PAC is able to converge in some of the games while Friends-QL isn't. An in-depth discussion on this matter would be valuable. My primary concern is that this observed discrepancy may simply stem from insufficient parameter tuning for Friends-QL, rather than any inherent limitations or advantages of the algorithms themselves.\n\nSince this is an empirical paper, I would expect evaluations on more challenging no-conflict problems. The only very challenging domains used in the evaluation are the Starcraft ones, which are adversarial. \n\nI would expect the paper to better explain a few core concepts used, so the reader could better understand the approach without having to rely on other papers. In particular, I have the following comments about presentation:\n\n1. An example of DCG would have helped answering some lingering questions, such as \"Why does Equation 19 can approximate the joint Q-value?\" \"How is a message passing algorithm useful at all?\"\n2. What are the input format used to train the neural model in each domain? \n3. What is the target network $\\hat{Q}$ used in Equation 18? If $\\hat{Q}$ is the target network, then what is $Q$?\n4. Algorithm 1 doesn't have inputs nor outputs, which makes it confusing to understand exactly what it does. \n5. Why is it an approximation in Equation 12? \n6. Why does inequality 14 hold true? \n7. What is the sum in Equation 11 over? All states in the state space? \n8. What is the expectation over at the bottom of page 2? \n9. Why is $\\pi_{a_{-i}}^+(a_{-i}|s, a_i)$ in Equation 12 conditioned on $a_i$?\n10. The plots aren't colorblind friendly. This is not acceptable. \n\nOther minor comments with respect to presentation:\n\n1. The sentence \"There is no incentive for any of the agents to deviate from that equilibrium\" is awkward because this is the very definition of an equilibrium. \n2. In the caption of Figure 2(b) should read $\\pi_2^+(B) = 0$ instead of $\\pi_2^+(A) = 0$. \n3. The design choices shown in Figure 3 doesn't address the issue with the exponential growth of the number of actions, but only mitigates it. The last sentence in the third paragraph of Section 3.3 needs rewording. \n4. The paper should cite SARSA in the paragraph above the pseudocode. \n5. The paragraph describing the Level-Based Foraging is quite rough, please review it carefully.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces Pareto Actor-Critic (PAC), an actor-critic algorithm that is specialized in no-conflict games, where an agent maximizes the utility of all agents by maximizing its own utility. Other Reinforcement Learning algorithms were shown to not necessarily converge to a Pareto optimal equilibrium in this type of game. PAC, on the other hand, was shown to converge (or very close to converge) to the Pareto optimal equilibrium on all games evaluated. \n\nThe trick used to achieve such a result is to assume that the other players, denoted $-i$ follow a policy that maximizes player's $i$ utility. Intuitively, this is telling player $i$ that they should trust that the other players are also cooperative. While this will incentivize $i$ to converge to a Pareto optimal equilibrium, it will in turn also incentivize the other players to converge to the same equilibrium. \n\nPAC is also extended with a Deep Coordination Graph (DCG) to handle domains with many agents, as the number of actions grows exponentially with the number of players. The DCG is used to approximate the argmax operator used in Q-Learning. \n\nThe paper presents experiments on a variety of domains, including simple but informative normal-form games, grid-world domains, and two challenging problem domains from Starcraft. The results support the claims that PAC and PACDCG are able to converge to Pareto optimum equilibria.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like the authors to handle all my suggestions related to the presentation of the paper. While it would be nice to see experiments on more challenging no-conflict games, this is not a requirement for me to recommend acceptance. The claims the authors made are already backed up by empirical evidence. \n\nI also would like to see an in-depth discussion on the reasons why PAC is able to converge on some of the domains where Friends-QL isn't.", "broader_impact_concerns": "I don't have any broader impact concerns with this submission.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3LFnD2lTvJ", "reviewer": "Reviewer_oaYN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I really love the topic of the paper, which is considering (semi-) cooperative games, and identifying algorithms that are likely to converge to a high welfare equilibrium. The authors also do a good job illustrating the issues arising with exploration and non-stationarity that result in converging to possibly low outcome results. \n\nThe empirical analysis is on relatively few games, and with reasonable MARL baselines, but is quite illuminating. \n\nI think the paper could benefit from extending the empirical results a bit, and also from improving on the presentation and the writing. See below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers the problem of equilibrium selection in multi agent games, seeking a Pareto optimal equilibrium among the set of possible equilibria. Many existing MARL algorithms may not converge or converge to a low social welfare outcome as agents are uncertain about the policies of other players. The authors propose an approach called Pareto Actor Critic (ParetoAC) which is a variant on traditional actor critic RL algorithms, that is tailored to no-conflict games (which contains cooperative games, but is not as restrictive), and aims at maximizing social welfare, or converging to a Pareto-optimal equilibrium. \n\nThe empirical analysis in the paper considers several interesting multi agent games, and shows that the proposed approach achieves higher total returns than existing known MARL approaches, and shows convergence to a Pareto optimal equilibrium in various matrix games. The authors also show a GNN based extension, which scales well to games with many agents. \n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "First, it would be good to include a more in depth discussion of MARL as a whole. For instance, it would be good to include a table with types of games (competitve, two player zero sum, many player zero sum, social dilemmas, no-conflict games and cooperative games). For each of those, a few key games falling in this class could be mentioned, as well as results indicating convergence to sub-optimal outcomes (for multiple of the baselines that you have mentioned). \n\nAlso, it would be good to include a more detailed high level diagram of the method that you proposed, and the key building blocks, early in the paper. The algorithm is brough in full a bit later, but an early introduction would be welcome. \n\nIn terms of the empirical results, I think a slight extension / discussion of other known results on MARL in Cooperative settings would be very welcome, as well as trying several know semi-coopertive games. One example is congestion games, where agents attempt to avoid selecting the same resources (as congested resources are more costly to use - see Wikipedia), and another example might be an extension of boulder push where the are multiple boulders (say 3) and multiple agents (say 6), so agents have to partition into teams (or possibly where only one boulder may be moved at the same time). As is, the empirical results are for somewhat limited settings. \n\nFinally, you examine a non-cooperative game theoretic solution (e.g. Nash). I think it would also be interesting to comment on Cooperative game theory / coalitional game theory solutions (e.g. the Core) - is there anything you can say here about RL being used for team formation or ad-hoc teamwork in these environments. Similarly, the algorithm was proposed for cooperative environment, but it would be interesting to examine what it does in mixed motive settings - could you comment on that? \n\nAll in all, this is very interesting work, and I think this would likely be pursued by further researchers examining more cooperative games. Currently there is a lot of work on competitive settings or mixed-motive ones, but less on cooperative games. \n", "broader_impact_concerns": "No substantive concerns that I can see. \n\nI would mention in the paper that Cooperative AI where agents collaborate with one another could be used for bad purposes, e.g. consider a set of agents who are cooperative to collude in an auction. But this concern relates to any work on cooperating agents. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "NgrI1BWeOX", "reviewer": "Reviewer_t3RA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The problem is well-motivated. The presentation is very clear. The approach is sound. Empirical results are fairly strong.\n\nWeaknesses: It is somehow restricted to no-conflict games. Some theoretical justification are missing.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies selecting Pareto-optimal equilibrium in non-conflict games through deep multiagent reinforcement learning. The authors proposed Pareto Actor-Critic, a deep MARL algorithm where every player's objective function assumes opponents always maximize for its own utilities. The authors derived the policy gradient update, where it learns an approximate joint Q function to derive opponents' lenient actions. To address the exponential cost when selecting the opponents' joint action the authors proposed learning a deep coordination graph to decompose the computation cost. The author presents empirical results where PAC outperforms baseline algorithms in reaching Pareto-optimal equilibria.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Some questions that I hope the authors can address:\n\n(1) Can the author elaborate more on the objective function (11). Why the trajectory distribution is on-policy while the values are assumed to be the optimistic one. Can one switch them and how would that affect the approach.\n\n(2) Why maximizing the per-timestep joint action of the opponents in equation (17) optimizing the objective (11). Is it possible to derive a convergence result based on Markovian properties.\n\n(3) An MARL algorithm that chooses opponents' joint action to maximize its own Q-value sounds familiar to me. Can the authors compare your approach to the ones in the following papers.\n[1] The Dynamics of Reinforcement Learning in Cooperative Multiagent Systems. Claus & Boutiiler\n[2] Reinforcement Learning to Play an Optimal Nash Equilibrium in Team Markov Games. Wang & Sandholm\n\n(4) Is it possible to generalize your approach to domains beyond no-conflict games? And how should you modify the algorithms to account for more general domains?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All of the major points brought up in review appear to have been addressed by the authors. However, please double-check to ensure that all of the reviewers' points have been addressed and upload a new version, if necessary.

There are no requirements to make changes, but please add author names and affiliations for the camera-ready copy.
Decision: Accept (poster)