Semi-Centralised Multi-Agent Reinforcement Learning with
Policy-Embedded Training

Multi-agent reinforcement learning (MARL) has emerged as a powerful tool to enable autonomous agents to tackle difficult tasks such as ride-sharing zhou2020smarts and swarm robotics mguni2018decentralised. Recently, various methodologies have produced significant performance boosts for MARL algorithms mguni2021ligs; kuba2021settling. Nevertheless, an important impediment for MARL is the high variance of the critic and policy gradient estimators. Reducing this variance is a critical challenge since high variance estimates can significantly hinder training, leading to low sample efficiency and poor overall performance gu2016q. This variance has multiple causes. First, MARL methods are applied to unknown environments whose reward signals are often noisy, especially as the sizes of the state and action spaces increases kuba2021settling. Second, unlike in single agent reinforcement learning (RL), MARL agents are faced with the challenge of distinguishing the aleatoric uncertainty due to environmental stochasticity from randomness due to agents’ exploratory actions. These challenges can deeply undermine the performance of MARL methods, especially in centralised learning (CL) methods where agents rely on observations of others’ actions while training.

CL serves as the foundation for many popular MARL methods such as MAPPO yu2021surprising, Q-DPP yang2020multi QMIX rashid2018qmix, SPOT-AC mguni2021learning, and COMA foerster2018counterfactual. In CL, each agent has a (possibly shared) critic that makes use of all available information generated by the system, including the global state and the joint action peng2017multiagent. Accounting for actions of other agents is crucial to achieve good coordination. Despite the obvious advantages from using knowledge of the joint actions in the critic, this methodology has several weaknesses that exacerbate the MARL variance problem. The Q-functions are based on one-off observations of actions sampled from other agents’ policies at a given state. This can produce VF updates based on improbable events and hence, inaccurate estimates of expected returns, leading to higher variance value function (VF) estimates. Also, since each agent’s critic has an explicit dependence on the actions of others, the CL critic suffers from an explosive growth in complexity with the number of agents yang2020overview. This results in CL methods needing large numbers of samples to complete training. Current methods for alleviating this rely on VF factorisations that require restrictive representational constraints. These constraints can cause poor exploration and performance failures when violated mahajan2019maven (e.g., QMIX rashid2018qmix requires a monotonicity constraint that can produce suboptimal value approximation).

Because of these issues affecting CL, (decentralised) independent learning (IL) represents an attractive alternative de2020independent. IL decomposes a MARL problem with $N$ agents into $N$ decentralised single-agent problems while the agents train solely with local observations. This avoids the explosive growth in complexity suffered by CL methods. Nonetheless, since MARL environments consist of multiple learners, IL suffer from convergence issues yang2020overview. Additionally, since IL methods cannot explicitly factor in the behaviour of other agents, achieving coordination among IL agents can be a difficult to achieve, resulting in suboptimal performance in some tasks.

To tackle these challenges, in this paper we propose a new MARL training formalism which we call semi-centralised training. In this framework, the agents use knowledge of other agents’ policies to compute accurate VFs estimates while using a critic (and policy) that has only the agent’s own action and state as an input. Specifically, we introduce policy embedding, a technique that enables the agents’ VF estimates to capture the present and future behaviour of other agents. As with parameter sharing, a technique used in many MARL methods (e.g., MAPPO yu2021surprising, QMIX rashid2018qmix), this procedure requires the agents to communicate their individual policies during training.

Our framework, policy embedding reinforcement learning algorithm (PERLA), embeds the agents’ policies within the critic estimation. This is done by sampling the actions of other agents and using them to marginalise the influence of other agents from the critic. The method is scalable and the resulting critic retains a functional form that requires only the agent’s own action (and state) as input to the action-value function. Consequently, the resulting critic exhibits the efficient scaling benefits of a fully decentralised critic while preserving the convergence guarantees and coordination abilities of a centralised critic.

Many leading MARL methods such as MAPPO yu2021surprising, IPPO de2020independent, MADDPG lowe2017multi use the actor-critic formalism. For concreteness, we instantiate our methodology within actor-critic architectures which involve both critic and policy updates which is a natural candidate to instantiate our framework. We propose Algorithm 1, which is a PERLA version of MAPPO/IPPO and show it improves the performance of the underlying algorithm. Applications of PERLA could naturally be extended to other degenerate architectures (e.g. value-based methods).

We summarise the advantages of PERLA below.
1) PERLA enables (networked) MARL agents to scale efficiently by factoring the joint policy into a new functional representation of the critic. Crucially, each agent’s critic does not use a joint action input. This enables efficient scaling with the number of agents without restrictive VF constraints (validated empirically in Sec. 5.2).
2) Elimination of non-stationarity of IL by incorporating updated policies into the agents’ critics through the policy embedding procedure. This avoids the non-stationarity problem in MARL when critics use localised observations.
3) Plug & play enhancement because PERLA can seamlessly incorporate different Actor-Critic algorithms, PERLA significantly boosts performance over the base MARL learners PPO schulman2017proximal, and MAPPO yu2021surprising (validated empirically Sec. 5.1).
4) PERLA is theoretically sound and we prove that
i) PERLA induces a vast reduction of variance of VF estimates (Theorem 1), ii) PERLA preserves policy gradient estimators (Theorem 3), and iii) Actor-Critic style algorithm based on PERLA converges almost surely to a locally optimal policy profile (Theorem 6).

Centralised Learning CL is assured to generate policies that are consistent with the desired system goal whenever the IGM principle son2019qtran is satisfied.¹¹1The IGM principle imposes an equivalence between the joint greedy action and the collection of individual greedy actions. In order to realise the IGM principle in the CL framework, QMIX and VDN propose two sufficient conditions of IGM to factorise the joint action-value function. Such decompositions are limited by the joint action-value function class they can represent and can perform badly is systems that do not adhere to these conditions wang2020qplex. QPLEX wang2020qplex uses a dueling network architecture to factor the joint action-value function. It however has been shown to fail in simple tasks with non-monotonic VFs rashid2020weighted. QTRAN son2019qtran formulates the MARL problem as a constrained optimisation problem but has been shown to scale poorly in complex MARL tasks such as the StarCraft Multi-Agent Challenge (SMAC) peng2020facmac. WQMIX rashid2020weighted considers a weighted projection towards better performing joint actions but does not guarantee IGM consistency. Actor-critic methods such as COMA foerster2018counterfactual and MADDPG lowe2017multi are popular methods within MARL. Although these methods use CL without restrictive assumptions, they are significantly outperformed by value-based methods such as QMIX and MAPPO yu2021surprising on standard MARL benchmarks like SMAC peng2020facmac. Consequently, achieving full expressiveness of the IGM function class with scalability remains an open challenge for MARL.

We formulate the MARL problem as a Markov game (MG) deng2021complexity, which is represented by a tuple $G=⟨N,S,{\left(A_i\right)}_{i\in N},P,R_i,\gamma ⟩$ where $S$ is the finite set of states, $A_i$ is an action set for agent $i\in N$, and $R_i:S\times A\to P\left(D\right)$ is the reward function that agent $i$ seeks to maximise (where $D$ is a compact subset of $R$), and $P:S\times A\times S\to [0,1]$ is the probability function describing the system dynamics where $A:={\times }_{i=1}^N{A}_i$. We consider a partially observable setting, in which given the system state $s^t\in S$, each agent $i\in N$ makes local observations ${\tau }_i^t=O(s^t,i)$ where $O:S\times N\to Z_i$ is the observation function and $Z_i$ is the set of local observations for agent $i$. To decide its actions, each agent $i\in N$ samples its actions from a Markov policy ${\pi }_{i,{\theta }_i}:Z_i\times A_i\to [0,1]$, which is parameterised by the vector ${\theta }_i\in R^d$. Throughout the paper, ${\pi }_{i,{\theta }_i}$ is abbreviated as ${\pi }_i$. At each time $t\in 0,1,\dots ,$ the system is in state $s^t\in S$ and each agent $i\in N$ takes an action $a_i^t\in A_i$, which together with the actions of other agents $a_{-i}^t:=(a_1^t,\dots ,a_{i-1}^t,a_{i+1}^t,\dots ,a_N^t)$, produces an immediate reward $r_i\sim R(s^t,a_i^t)$ for agent $i\in N$. The system then transitions to a next state $s^{t+1}\in S$ with probability $P(s^{t+1}|s^t,a^t)$ where $a^t=(a_1^t,\dots ,a_N^t)\in A$ is the joint action which is sampled from the joint policy $\pi :={\prod }_{i=1}^N{\pi }_i$. The goal of each agent $i$ is to maximise its expected returns measured by its VF $v_i\left(s\right)=E\left[{\sum }_{t=0}^{\infty }{\gamma }^t{R}_i\right(s^t,a^t)|s_0=s]$ and the action-value function for each agent $i\in N$ is given by $Q_i(s,a)=E\left[{\sum }_{t=0}^{\infty }{R}_i\right(s^t,a^t)|a^0=a]$, where $-i$ denotes the tuple of agents excluding agent $i$. Likewise, we denote ${\prod }_{j=1,j\ne i}^N{\pi }_j$ as ${\pi }_{-i}$. In the fully cooperative case all agents share the same goal: $R_1=\dots R_N:=R$.

In the CL paradigm, given a state $s\in S$ and the joint action $a\in A$, each agent $i\in N$ computes its action-value function $Q_i(s,a)$. The action-value function provides an estimate of the agent’s expected return using its policy given the behaviour of all other agents $N/\left\{i\right\}$ for a given action $a_i\in A_i$. Therefore, $Q_i(s,a)$ seeks to provide an estimate of the agent’s own action, accounting for the actions of others. MARL agents use stochastic policies to explore — each joint action $a\sim \pi$ may contain exploratory actions that included in agent policy updates.

The core component of the PERLA framework is a Critic Policy Embedding procedure. As the name suggests, the procedure embeds the agents’ policies within the critic, enabling us to construct a critic whose input takes only the agent’s own action and the state while factoring in the joint behaviour of other agents. This is done by jointly marginalising the action-value function $\tilde{Q}$, as defined below:

where $s\in S,a_i\sim {\pi }_i(\cdot |{\tau }_i),a_{-i}\sim {\pi }_{-i}(\cdot |{\tau }_{-i})$. This object requires some explanation: as with $Q_i$, the function ${\tilde{Q}}_i$ seeks to estimate the expected return following agent $i$ taking action $a_i$. However, unlike $Q_i$, ${\tilde{Q}}_i$ builds in the distribution of the actions played by other agents under their current policy. This gives less weight to low probability actions and conversely for high probability actions. A key aspect is that $\hat{Q}$ depends only on the agent’s own action (and state) which acquires the scalability benefit of IL while factoring in the behaviour of other agents. As in practice, it may be impossible to analytically calculate 1, to approximate ${\tilde{Q}}_i(s,a_i)$, for any $s\in S$ and any $a_i\in A_i$ we construct the object $\hat{Q}$:

We now describe the implementation details of Actor-Critic algorithm using the critic policy embedding procedure, along with pseudocode in Algorithm 1:
1. Augment the critic $Q$ to accommodate joint action, i.e., $Q(s^t,a_i^t,a_{-i}^{t\left(j\right)})$.
2. Each agent $i$ communicates its policy ${\pi }_i$ and its local observation ${\tau }_i^t$ to other agents.
3. Upon arrival to state $s^t$ each agent $i$ samples other agents’ actions given their local observations, $k$ times using other agents’ policies $a_j\sim {\pi }_j\left(a_j|{\tau }_j^t\right)$. This produces joint samples of the actions $\{a_{-i}^{t\left(j\right)}{\}}_{j=1}^k$ for each time step $t$.
4. Each agent uses this to approximate the function
${\tilde{Q}}_i(s^t,a_i^t)=\frac{1}{k}{\sum }_{j=1}^{k}Q(s^t,a_i^t,a_{-i}^{t\left(j\right)})\approxeq {\hat{Q}}_i(s_t,a_i^t)$, embedding the behaviour of other agents.
5. Agent $i$ uses ${\tilde{Q}}_i$ as the critic to update its policy using the chosen policy gradient algorithm.
6. Return to 2 and repeat until termination.

In our experiments, we use a value-function style critic, where $Q(s^t,a_i^t,a_{-i}^{t\left(j\right)})=r_t+\gamma V(s^t,a_{-i}^{t\left(j\right)})$ and $V(s^t,a_{-i}^{t\left(j\right)})$ is approximated via a deep neural network. In this case, it is enough to marginalise the next step values function. To perform policy updates, we use PPO updates schulman2017proximal. We apply PERLA to two cases, one which involves a base learner whose critic input captures global information (MAPPO yu2021surprising) and another base learner whose critic input is only local observations (IPPO) (in both cases, PERLA makes use of shared global state information during training). This gives rise to PERLA MAPPO and PERLA IPPO algorithms respectively.

In this section, we perform a detailed theoretical analysis of PERLA. Here, we derive theoretical results that establish the key benefits of PERLA, namely that it vastly reduces variance of the key estimates used in training. We begin with a result that quantifies the reduction of variance when using ${\hat{Q}}_i$ instead of $Q_i$. We defer all proofs to the Appendix.

Therefore for $k=1$ we get that the approximation has the same variance as the non-marginalised Q-function. However, for any $k>1$ the approximation to marginalised Q-function has smaller variance that the non-marginalised Q-function. Therefore marginalisation procedure of PERLA can essentially be used as a variance reduction technique. Let us now analyse how this framework can be applied to enhance multi-agent policy gradient algorithm, which is known to suffer from high variance in its original version.

In the policy gradient algorithms, we assume a fully cooperative game which avoids the need to add the agent indices to the state-action and state-value functions since the agents have identical rewards. The goal of each agent is therefore to maximise the expected return from the initial state defined as $J\left(\theta \right)=E_{s_0\sim p\left(s_0\right)}\left[v\right(s_0\left)\right]$, where $p\left(s_0\right)$ is the distribution of initial states and $\theta =({\theta }_1^T,\dots ,{\theta }_N^T{)}^T$ is the concatenated vector consisting of policy parameters for all agents. The following well-known theorem establishes the gradient of $J\left(\theta \right)$ with respect to the policy parameters.

Therefore, to calculate the gradient with respect to policy parameters, it is necessary to make use of the state-action-values. In practice, it can estimated by a function approximator, which gives rise to Actor-Critic methods konda1999actor. In MARL, one can either maintain a centralised critic that provides state-action-value for the $i^{th}$ agent using the knowledge of the other agents’ actions or introduce a decentralised critic that does not take actions of others (in its inputs). This gives rise to the centralised training decentralised execution (CT-DE) $g_i^{\text{C}}$ and decentralised $g_i^{\text{D}}$ gradient estimators respectively, as defined below.

where $Q(s_t,a_{-i}^t,a_i^t)$ and $\tilde{Q}(s^t,a_i^t)$ are the CT-DE and decentralised critics respectively. In PERLA Actor-Critic algorithms (such as in Algorithm 1) we utilise a third estimator - the PERLA estimator given below:

where $\hat{Q}(s^t,a_i^t)$ is the Monte-Carlo approximation of $\tilde{Q}(s^t,a_i^t)$. Note that in this approach we maintain a centralised critic $Q(s^t,a_{-i}^t,a_i^t)$, therefore the approximation to the marginalised Q-function is obtained using $\hat{Q}(s^t,a_i^t)=\frac{1}{k}{\sum }_{j=1}^{k}Q(s^t,a_i^t,a_{-i}^{t\left(j\right)})$, where $a_{-i}^{t\left(j\right)}\sim {\pi }_{-i}\left(a_{-i}^t|{\tau }_{-i}^t\right)$. The PERLA estimator is equal in expectation to the CT-DE estimator as stated by the following Theorem.

Therefore, whenever the critic provides the true Q-value, PERLA estimator is an unbiased estimate of the policy gradient (which follows from Theorem 2). However, although the CT-DE and PERLA estimators have the same expectations, the PERLA estimator enjoys significantly lower variance. Similar to the analysis in kuba2021settling, let us study the excess variance those two estimators have over the decentralised estimator. Let $B_i$ be the upper bound on the gradient norm of $i$th agent, i.e. $B_i={sup}_{s,a}\left|\left|{\nabla }_{{\theta }^i}\log {\pi }_i\left(a_i|s\right)\right|\right|$ and $C$ be the upper bound on the Q-function, i.e. $C={sup}_{s,a}Q(s,a)$.

We can now present two theorems showing the effectiveness of PERLA estimator for policy gradients.

Therefore, we can see that with $k=1$ the bound on excess variance of the PERLA estimator is the same as for the CT-DE estimator, but as $k\to \infty$, the variance of PERLA estimator matches the one of the fully decentralised estimator. However, this is done while still maintaining a centralised critic, unlike in the fully decentralised case. It turns out that the presence of centralised critic is critical, as it allows us to guarantee the converge of an algorithm to a local optimum with probability 1. The result is stated by the next Theorem.

We present a proof sketch here and defer the full proof to Appendix Proof of Theorem 6.
The proof consists of showing that a multi-agent Actor-Critic algorithm using policy gradient estimate $g_i^P$ or $g_i^C$ is essentially a special case of single-agent Actor-Critic. Note that because the decentralised critic does not allow us to query the state-action-value for joint action of all agents, a decentralised actor-critic using $g_i^D$ as policy gradient estimate is not equivalent to the single-agent version and we cannot establish convergence for it. Therefore, our PERLA estimator enjoys both the low variance property of the decentralised estimator and the convergence guarantee of the CT-DE one. Additionally, having a centralised critic yields better performance in practice in environments with strong interactions between agents kok2004sparse.

We ran a series of experiments in Large-scale Matrix Games (son2019qtran), Level-based Foraging (LBF) (christianos2020shared), Multi-agent Mujoco de2020deep and the StarCraft II Multi-agent Challenge (SMAC) samvelyan2019starcraft²²2The specific maps/variants used of each of these environments in given in Section B of the Appendix) to test if PERLA: 1. Improves overall performance of MARL base learners. 2. Enables efficient scaling in the number of agents. 3. Reduces variance of value function estimates. In all tasks, we compared the performance of PERLA against MAPPO (yu2021surprising) and IPPO de2020independent. Here, we report average training results across multiple maps for LBF and SMAC. Further performance comparisons across these maps are deferred to the Appendix. Lastly, we ran a suite of ablation studies which we deferred to the Appendix.

We used the codebase accompanying the MARL benchmark study in papoudakis2021benchmarking to implement PERLA on top IPPO schulman2017proximal and MAPPO yu2021surprising. IPPO is a decentralised learning algorithm, while MAPPO follows the CT-DE paradigm. Implementing PERLA on both widely used training paradigms enables us to examine the impact of PERLA in each case. Hyperparameters were tuned using simple grid-search, and the values over which we tuned them are presented in Table 3 in the Appendix. All results are statistics of the metric being measured over $3$ random seeds unless otherwise stated. In our plots dark lines represent the mean across the seeds, while shaded areas represent 95% confidence intervals.

MARL estimators suffer from high variance due to a number of sources of randomness. This hinders learning and reduces the sample efficiency of MARL methods. Secondly, many leading CT-DE algorithms avoid exponential scaling complexity at the expense of employing representational constraints that impose strong restrictions. Despite the popularity of the CT-DE paradigm, its efficacy is heavily constrained by limits imposed by these challenges. On the other hand, IL often depend on random instances of coordination to solve tasks which can lead to poor sample efficiency and learning failures. Consequently, scalability and efficient learning are key challenges in MARL research.

We introduced PERLA, a plug & play enhancement tool that enables MARL to scale efficiently while inducing sample efficient, coordinated learning among MARL agents. Our theory and empirical analyses show that PERLA reduces the variance of VF estimators which is critical for efficient learning. By introducing a policy embedding protocol which factors in the behaviour of other agents in the critic functional representation, PERLA avoids joint action input spaces to train MARL critics. In this way, PERLA enables MARL to exhibit the scalability benefits of IL while achieving coordinated learning, often required to achieve optimal performance. This unlocks the capacity for coordinated behaviours amog MARL agents whose critic structure resembles that of IL agents. In doing so, PERLA powerfully bridges the gap between MARL and single agent RL.