Distributed Multi-Agent Reinforcement Learning with One-hop Neighbors and Compute Straggler Mitigation

Recent years have witnessed tremendous success of reinforcement learning (RL) in challenging decision making problems, such as robot control and video games. Research efforts are currently focused on multi-agent settings, including cooperative robot navigation [1], multi-player games [2], and traffic management [3]. Direct application of RL techniques in multi-agent settings by running single-agent algorithms simultaneously on each agent exhibits poor performance [4]. This is because, without considering interactions among the agents, the environment becomes non-stationary from the perspective of a single agent.

Multi-agent reinforcement learning (MARL) [5] addresses this challenge by considering all agents and their dynamics collectively when learning the value function and policy of an individual agent. Most effective MARL algorithms, such as multi-agent deep deterministic policy gradient (MADDPG) [4] and counterfactual multi-agent (COMA) [6], adopt this strategy. However, learning a joint-state value or action-value (Q) or policy function is challenging due to the exponentially growing joint state and action spaces with increasing number of agents [7, 8]. Policies trained with joint state-action pairs have poor performance in large-scale settings as demonstrated in recent work [9, 10], because their accurate approximation requires models with extremely large capacity.

MARL algorithms that improve the quality of learned policies for large-scale multi-agent settings often employ value function factorization that factorizes the global value/Q function into individual value/Q functions depending on local states and actions, e.g., as in Value Decomposition Network (VDN) [11], QMIX [12], QTran [13], mean-field MARL (MFAC) [9] or scalable actor critic (SAC) [8]. In addition to value factorization, there are several other methods proposed to enable scalable MARL. MAAC [14] uses an attention module to abstract states of other agents when training an agent’s Q function, which reduces the quadratically increasing input space to a linear space. EPC [10] applies curriculum learning to gradually scale MARL up. While these methods achieve great policy performance, the training time can be significant when the number of agents increases because these methods cannot be easily trained in an efficient distributed or parallel manner over multiple computers.

To address the challenge of training policies for large numbers of agents over a distributed computing architecture, we propose a MARL algorithm called Distributed multi-Agent Reinforcement Learning with One-hop Neighbors (DARL1N). DARL1N’s main advantage over state-of-the-art MARL methods is that it allows distributed training across compute nodes (devices with networking, storage, and computing capabilities) running in parallel, with each compute node simulating only a very small subset of the agent transitions. This is made possible by modeling the agent team topology as a proximity graph and representing the Q function and policy of each agent as a function of its one-hop neighbors only. This structure significantly reduces the representation complexity of the Q and policy functions and yet maintains expressiveness when training is done over varying states and numbers of neighbors. Furthermore, when agent interactions are restricted to one-hop neighborhoods, training an agent’s Q function and policy requires transitions only of the agent itself and its potential two-hop neighbors. This enables highly efficient distributed training because each compute node needs to simulate only the transitions of the agents assigned to it and their two-hop neighbors.

RL or MARL policies can be trained over a distributed computing architecture in either a centralized [15, 16] or decentralized [17] manner. Decentralized architectures [17] offer greater resilience to node failures and malicious attacks but introduce significant communication overhead as frequent information exchanges are required. Additionally, achieving global coordination in such systems is inherently challenging: global information must either be inferred under the assumption of globally observable states, which limits its applicability, or obtained through consensus, which is difficult to achieve in large-scale systems. In contrast, centralized architectures with a central controller are more communication-efficient and facilitate easier global coordination, with communication occurring either asynchronously [18] or synchronously [19]. Asynchronous training faces multiple challenges including slow convergence, difficult debugging and analysis, and sometimes subpar quality of learned policies as learners may return stale gradients evaluated with old parameters [20, 21, 22, 19, 23]. Synchronous training is superior in these aspects but is vulnerable to computing stragglers [24] that are common in wireless and mobile networks. These stragglers, which are slow or unresponsive compute nodes caused by communication bottlenecks or software and hardware issues, can result in delays or failures in the training process. Coded computation [25] that employs coding theory to introduce redundant computation can mitigate computing stragglers. While extensively explored in various distributed computation problems such as matrix multiplication [25], linear inverse problems [26], convolution [27], and map reduce [28], its application for MARL remains under-studied. In our previous work [16], we explored the merits of coded computation in enhancing resilience and accelerating the training of MADDPG [16] in a distributed manner. Building upon this, in this paper, we propose a coded distributed learning architecture tailored for DARL1N. Unlike the one introduced in [16], where the central controller simulates global environment interactions among all agents and sends simulation data to each learner to train an agent, in the new architecture, each learner directly simulates local environment interactions among a small set of neighboring agents during individual agent training and thus improves distributed computing efficiency and reduces communication overhead.

Contributions: The primary contribution of this paper is a new MARL algorithm called DARL1N, which employs one-hop neighborhood factorization of the value and policy functions, allowing distributed training with each compute node simulating a small number of agent transitions. DARL1N supports highly-efficient distributed training and generates high-quality multi-agent policies for large agent teams. The second contribution is a novel coded distributed learning architecture for DARL1N called Coded DARL1N, which allows individual agents to be trained by multiple compute nodes simultaneously, enabling resilience to stragglers. Our analysis shows that introducing redundant computations via coding theory does not introduce bias in the value and policy gradient estimates, and the training converges similarly to stochastic gradient descent-based methods. Four codes including Maximum Distance Separable (MDS), Random Sparse, Repetition, and Low Density Generator Matrix (LDGM) codes are investigated to introduce redundant computation. Moreover, we conduct comprehensive experiments comparing DARL1N with four state-of-the-art MARL methods, including MADDPG, MFAC, EPC and SAC, and evaluating their performance in different RL environments, including Ising Model, Food Collection, Grassland, Adversarial Battle, and Multi-Access Wireless Communication. We also conduct experiments to evaluate the resilience of Coded DARL1N to stragglers when trained under different coding schemes.

It is noted that DARL1N was first presented in a short conference version [29]. Differing from this version, this journal article further extends DARL1N by introducing a new coded distributed learning architecture to enhance its resilience to stragglers while also improving training efficiency. Theoretical analysis is conducted to elucidate the convergence of Coded DARL1N. Additionally, this journal undertakes a more comprehensive experimental study, encompassing not only the performance of DARL1N but also its new coded variant. It includes additional benchmarks, environments, and evaluation metrics for a more thorough assessment from various aspects.

In the rest of the paper, Sec. 2 formulates the MARL problem to be addressed and describes the occurrence of stragglers within distributed learning systems. The proposed DARL1N algorithm is then introduced in Sec. 3, followed by the coded distributed learning architecture and different coding schemes, which are described in Sec. 4 and Sec. 5, respectively. Experiment results are presented in Sec. 6. Limitations and future work are discussed in Sec. 7. Finally, Sec. 8 concludes the paper.

In MARL, $M$ agents learn to optimize their behavior by interacting with the environment. Denote the state and action of agent $i\in[M]:=\{1,\ldots,M\}$ by $s_{i}\in\mathcal{S}_{i}$ and $a_{i}\in{\cal A}_{i}$, respectively, where ${\cal S}_{i}$ and ${\cal A}_{i}$ are the corresponding state and action spaces. Let $\mathbf{s}:=(s_{1},\ldots,s_{M})\in\mathcal{S}:=\prod_{i\in[M]}\mathcal{S}_{i}$ and $\mathbf{a}:=(a_{1},\ldots,a_{M})\in\mathcal{A}:=\prod_{i\in[M]}\mathcal{A}_{i}$ denote the joint state and action of all agents. At time $t$, a joint action $\mathbf{a}(t)$ applied at state $\mathbf{s}(t)$ triggers a transition to a new state $\mathbf{s}(t+1)\in{\cal S}$ according to a conditional probability density function (pdf) $p(\mathbf{s}(t+1)|\mathbf{s}(t),\mathbf{a}(t))$. After each transition, each agent $i$ receives a reward $r_{i}(\mathbf{s}(t),\mathbf{a}(t))$, determined by the joint state and action according to the function $r_{i}:{\cal S}\times{\cal A}\mapsto\mathbb{R}$. The objective of each agent $i$ is to design a policy $\mu_{i}:{\cal S}\rightarrow{\cal A}_{i}$ to maximize the expected cumulative discounted reward (known as the value function):

where $\boldsymbol{\mu}:=\left(\mu_{1},\ldots,\mu_{M}\right)$ denotes the joint policy of all agents and $\gamma\in(0,1)$ is a discount factor. Alternatively, an optimal policy $\mu_{i}^{*}$ for agent $i$ can be obtained by maximizing the action-value (Q) function:

and setting $\mu_{i}^{*}(\mathbf{s})\in\arg\max_{a_{i}}\max_{\mathbf{a}_{-i}}Q_{i}^{*}(\mathbf{s},\mathbf{a})$, where $Q_{i}^{*}(\mathbf{s},\mathbf{a}):=\max_{\boldsymbol{\mu}}Q_{i}^{\boldsymbol{\mu}}(\mathbf{s},\mathbf{a})$ and $\mathbf{a}_{-i}$ denotes the actions of all agents except $i$.

To develop a distributed MARL algorithm, we impose additional structure on the MARL problem. Assume that all agents share a common state space, i.e., ${\cal S}_{i}={\cal S}_{j}$, $\forall i,j\in[M]$ and let $\operatorname*{dist}:{\cal S}_{i}\times{\cal S}_{i}\rightarrow\mathbb{R}$ be a distance metric on the state space. Note that the distance metric can also be defined over a common state subspace. However, for notation simplicity, a common state space is assumed here. Consider a proximity graph [30] that models the topology of the agent team. A $d$-disk proximity graph is defined as a mapping that associates the joint state $\mathbf{s}\in{\cal S}$ with an undirected graph $({\cal V},{\cal E})$ such that ${\cal V}=\{s_{1},s_{2},\ldots,s_{M}\}$ and ${\cal E}=\{(s_{i},s_{j})|\operatorname*{dist}(s_{i},s_{j})\leq d,i\neq j\}$. Define the set of one-hop neighbors of agent $i$ as ${\cal N}_{i}:=\{j|(s_{i},s_{j})\in{\cal E}\}\cup\{i\}$. We make the following assumption about the agents’ motion.

This assumption is satisfied in many problems where, e.g., due to physical constraints, the agent states can only change by a bounded amount in a single time step.

Define the potential neighbors of agent $i$ at time $t$ as ${\cal P}_{i}(t):=\{j|\operatorname*{dist}(s_{j}(t),s_{i}(t))\leq 2\epsilon+d\}$, which captures the set of agents that may become one-hop neighbors of agent $i$ at time $t+1$. Denote the joint state and action of the one-hop neighbors of agent $i$ by $\mathbf{s}_{{\cal N}_{i}}=(s_{j_{1}},\ldots,s_{j_{|{\cal N}_{i}|}})$ and $\mathbf{a}_{{\cal N}_{i}}=(a_{j_{1}},\ldots,a_{j_{|{\cal N}_{i}|}})$, respectively, where $j_{1},\ldots,j_{|{\cal N}_{i}|}\in{\cal N}_{i}$. Our key idea is to let agent $i$’s policy, $a_{i}=\mu_{i}(\mathbf{s}_{{\cal N}_{i}})$, only depend on the one-hop neighbor states $\mathbf{s}_{{\cal N}_{i}}$ instead of all agent states $\mathbf{s}$, and we assume that each agent can obtain its one-hop neighbor states through observation or communication. The intuition is that agents that are far away from agent $i$ at time $t$ have little impact on its current action $a_{i}(t)$. To emphasize that the output of a function $f:\prod_{i\in[M]}{\cal S}_{i}\mapsto\mathbb{R}$ is affected only by a subset ${\cal N}\subseteq[M]$ of the input dimensions, we use the notation $f(\mathbf{s})=f(\mathbf{s}_{{\cal N}})$ for $\mathbf{s}\in{\cal S}$ and $\mathbf{s}_{{\cal N}}\in\prod_{i\in{\cal N}}{\cal S}_{i}$ in the remainder of the paper. We make two additional assumptions on the problem structure to ensure the validity of our policy model.

This assumption can always be satisfied by setting $d$ to the full environment range. In this case, the one-hop neighbor reward assumption becomes the standard reward definition, which depends on states and actions of all agents and is applicable to general MARL problems. For environments with local reward models, a smaller distance value $d$ can be chosen based on the specific environment configuration. For example, in collision avoidance problems, an agent’s reward may depend only on the states and actions of nearby agents that maintain a safe distance. In multi-agent networks or sensing problems, the one-hop neighbors can be those within communication or observation range. Next, we make a similar assumption for agent $i$’s transition model.

The objective of each agent $i$ is to obtain an optimal policy $\mu_{i}^{*}$ by solving the following problem:

where $Q_{i}^{*}(\mathbf{s},\mathbf{a}):=\max_{\boldsymbol{\mu}}Q_{i}^{\boldsymbol{\mu}}(\mathbf{s},\mathbf{a})$ is the optimal action-value (Q) function introduced in the previous section.

The goal of this paper is to develop a MARL algorithm that (i) utilizes policy and value representations that scale favorably with the number of agents $M$ and (ii) allows efficient training on a distributed computing system containing compute stragglers.

This section develops the DARL1N algorithm to solve the MARL problem with proximity-graph structure introduced in Sec. 2. DARL1N considers the effect of the one-hop neighbors of an agent in representing its Q and policy functions, which allows updating the Q and policy function parameters using only local one-hop neighborhood transitions.

Specifically, the Q function of each agent $i$ can be expressed as a function of its one-hop neighbor states $\mathbf{s}_{{\cal N}_{i}}$ and actions $\mathbf{a}_{{\cal N}_{i}}$ as well as the states $\mathbf{s}_{{\cal N}_{i}^{-}}$ and actions $\mathbf{a}_{{\cal N}_{i}^{-}}$ of the remaining agents that are not immediate neighbors of $i$:

Inspired by the SAC algorithm [8], we approximate the Q value with a function $\tilde{Q}_{i}^{\boldsymbol{\mu}}$ that depends only on one-hop neighbor states and actions:

where the weights $w_{i}(\mathbf{s}_{{\cal N}_{i}},\mathbf{s}_{{\cal N}_{i}^{-}},\mathbf{a}_{{\cal N}_{i}},\mathbf{a}_{{\cal N}_{i}^{-}})>0$ satisfy $\sum_{\mathbf{s}_{{\cal N}_{i}^{-}},\mathbf{a}_{{\cal N}_{i}^{-}}}w_{i}(\mathbf{s}_{{\cal N}_{i}},\mathbf{s}_{{\cal N}_{i}^{-}},\mathbf{a}_{{\cal N}_{i}},\mathbf{a}_{{\cal N}_{i}^{-}})=1$. The approximation error is given in the following lemma.

We parameterize the approximated Q function $\tilde{Q}_{i}^{\boldsymbol{\mu}}(\mathbf{s}_{{\cal N}_{i}},\mathbf{a}_{{\cal N}_{i}})$ and the policy $\mu_{i}(\mathbf{s}_{{\cal N}_{i}})$ by $\theta_{i}$ and $\phi_{i}$, respectively. To handle the varying sizes of $\mathbf{s}_{{\cal N}_{i}}$ and $\mathbf{a}_{{\cal N}_{i}}$, in the implementation, we set the input dimension of $\tilde{Q}_{i}^{\boldsymbol{\mu}}$ to the largest possible dimension of $(\mathbf{s}_{{\cal N}_{i}},\mathbf{a}_{{\cal N}_{i}})$, and apply zero-padding for agents that are not within the one-hop neighborhood of agent $i$. The same procedure is applied to represent $\mu_{i}(\mathbf{s}_{{\cal N}_{i}})$.

To learn the approximated Q function $\tilde{Q}_{i}^{\boldsymbol{\mu}}$, instead of incremental on-policy updates to the Q function as in SAC [8], we apply off-policy temporal-difference learning with a buffer similar to MADDPG [4]. The parameters $\theta_{i}$ of the approximated Q function are updated by minimizing the following temporal difference error:

where ${\cal D}_{i}$ is a replay buffer for agent $i$ that contains information only from ${\cal N}_{i}$ and ${\cal N}^{\prime}_{i}$, the one-hop neighbors of agent $i$ at the current and next time steps, and the one-hop neighbors ${\cal N}^{\prime}_{l}$ for $l\in{\cal N}^{\prime}_{i}$. Data from the one-hop neighbors of the next-step one-hop neighbors ${\cal N}^{\prime}_{i}$ are needed to compute the next-step one-hop neighbors actions $\mathbf{a}_{{\cal N}_{i}^{\prime}}$. To stabilize the training, a target Q function $\hat{Q}_{i}^{\hat{\boldsymbol{\mu}}}$ with parameters $\hat{\theta}_{i}$ and a target policy function $\hat{\mu}_{i}$ with parameters $\hat{\phi}_{i}$ are used. The parameters $\hat{\theta}_{i}$ and $\hat{\phi}_{i}$ are updated using Polyak averaging: $\hat{\theta}_{i}=\tau\hat{\theta}_{i}+(1-\tau)\theta_{i},\hat{\phi}_{i}=\tau\hat{\phi}_{i}+(1-\tau)\phi_{i}$ where $\tau$ is a hyperparameter. In contrast to MADDPG [4], the replay buffer $\mathcal{D}_{i}$ for agent $i$ only needs to store its local interactions $(\mathbf{s}_{{\cal N}_{i}},\mathbf{a}_{{\cal N}_{i}},r_{i},\{\mathbf{s}_{{\cal N}_{l}^{\prime}}\}_{\forall l\in{\cal N}^{\prime}_{i}})$ with nearby agents, where $\{\mathbf{s}_{{\cal N}_{l}^{\prime}}\}_{\forall l\in{\cal N}^{\prime}_{i}}$ is required to calculate $\mathbf{a}_{{\cal N}_{i}^{\prime}}$. Also, in contrast to SAC [8], each agent $i$ only needs to collect its own training data by simulating local two-hop interactions, which reduces agents’ experience correlations and allows efficient distributed training as explained in Sec. 4.

Agent $i$’s policy parameters $\phi_{i}$ are updated using a gradient

where again data $\mathcal{D}_{i}$ only from local interactions is needed.

To implement the parameter updates proposed above, agent $i$ needs training data ${\cal D}_{i}=(\mathbf{s}_{{\cal N}_{i}},\mathbf{a}_{{\cal N}_{i}},r_{i},\{\mathbf{s}_{\mathcal{N}^{\prime}_{l}}\}_{l\in{\cal N}^{\prime}_{i}})$ from its one-hop neighbors at the current and next time steps. The relation between one-hop neighbors at the current and next time steps is captured by the following proposition.

Proposition 3.2 allows us to decouple the global interactions among agents and limit the necessary observations to be among one-hop neighbors. To collect training data, at each time step, agent $i$ first interacts with its one-hop neighbors to obtain their states $\mathbf{s}_{{\cal N}_{i}}$ and actions $\mathbf{a}_{{\cal N}_{i}}$, and compute its reward $r_{i}(\mathbf{s}_{{{\cal N}}_{i}},\mathbf{a}_{{\cal N}_{i}})$. To obtain $\mathbf{s}_{{\cal N}_{l}^{\prime}}$ for all $l\in{\cal N}^{\prime}_{i}$, we first determine agent $i$’s one-hop neighbors at the next time step, ${\cal N}^{\prime}_{i}$. Using Proposition 3.2, we let each potential neighbor $k\in{\cal P}_{i}$ perform a transition to a new state $s^{\prime}_{k}\sim p_{k}(\cdot|\mathbf{s}_{{{\cal N}}_{k}},\mathbf{a}_{{{\cal N}}_{k}})$, which is sufficient to determine ${\cal N}^{\prime}_{i}$. Then, we let the potential neighbors ${\cal P}_{l}$ of each new neighbor $l\in{\cal N}^{\prime}_{i}$ perform transitions to determine ${\cal N}_{l}^{\prime}$ and obtain $\mathbf{s}_{{\cal N}_{l}^{\prime}}$.

Fig. 1(a) illustrates the data collection process. At time $t$, agent $i$ obtains $\mathbf{s}_{{\cal N}_{i}}$, $\mathbf{a}_{{\cal N}_{i}}$, and $r_{i}(\mathbf{s}_{{\cal N}_{i}},\mathbf{a}_{{\cal N}_{i}})$ for ${\cal N}_{i}=\{i,1\}$. Then, the potential neighbors of agent $i$, ${\cal P}_{i}=\{1,2,i\}$, proceed to their next states at time $t+1$. This is sufficient to determine that ${\cal N}_{i}^{\prime}=\{i,2\}$ and obtain $\mathbf{s}_{{\cal N}^{\prime}_{i}}$. Finally, we let agent $3$, which belongs to set ${\cal P}_{2}=\{i,1,2,3\}$, perform a transition to determine that ${\cal N}_{2}^{\prime}=\{i,2,3\}$ and obtain $\mathbf{s}_{{\cal N}^{\prime}_{2}}$.

As each agent only needs to interact with one-hop neighbors to update its parameters, the agents can be trained in parallel on a distributed computing architecture, where each compute node only needs to simulate the two-hop neighbor transitions for agents assigned to it for training.

In this section, we introduce an efficient and resilient distributed learning architecture for training DARL1N. A coded distributed learning architecture, illustrated in Fig. 1(b), consists of a central controller and $N$ compute nodes, called learners. The central controller stores a copy of all parameters of the policy $\phi_{i}$, target policy $\hat{\phi}_{i}$, Q function $\theta_{i}$, and target Q function $\hat{\theta}_{i}$, for all $i\in[M]$. In each training iteration, the central controller broadcasts all agents’ parameters to all learners, who then calculate and return the gradients required for updating the parameters. In a traditional uncoded distributed learning architecture, each agent is only trained (with its policy and value gradients computed) by a single learner. If any learner becomes slow or unresponsive, i.e., a straggler, the whole training procedure is delayed or may fail. Our coded distributed learning architecture addresses the possible presence of stragglers in the computing system by introducing redundant computations. We let more than one learner train each agent, which not only improves the system resilience to stragglers but also accelerates the training speed, as we show in Sec. 6.2. To describe which learners are assigned to train each agent, we introduce an assignment matrix $\mathbf{C}\in\mathbb{R}^{N\times M}$ with non-zero entries $c_{j,i}\neq 0$ indicating that learner $j\in[N]$ is assigned to train agent $i\in[M]$. The complete set of learners assigned to train an agent $i$ can then be determined by $\{j|c_{j,i}\neq 0,\forall j\in[N]\}$. To construct the assignment matrix $\mathbf{C}$, we apply coding theory as explained in Sec.5.

To calculate the gradients for an agent $i$, each learner $j$ with $c_{j,i}\neq 0$ simulates transitions to get the interaction data $(\mathbf{s}_{{\cal N}_{i}},\mathbf{a}_{{\cal N}_{i}},r_{i},\{\mathbf{s}_{{\cal N}_{l}^{\prime}}\}_{l\in{\cal N}^{\prime}_{i}})$ as described in Sec. 3, which are stored in a replay buffer ${\cal D}_{j,i}$. After that, learner $j$ calculates the gradients of the temporal difference error needed for updating the Q function parameters $\theta_{i}$ of agent $i$ using (3) and updating the policy parameters $\phi_{i}$ using (4).

As the replay buffer ${\cal D}_{j,i}$ can have a large size, to improve efficiency, we use a mini-batch ${\cal B}_{j,i}$ uniformly sampled from ${\cal D}_{j,i}$ to estimate the expectations in (3)-(4). In particular, the temporal difference error in (3) is estimated with:

Similarly, the gradients used to update policy parameters are estimated with:

Let $\hat{\mathbf{e}}_{j,i}=[\nabla\hat{{\cal L}}_{j}(\theta_{i}),\hat{\mathbf{g}}_{j}(\phi_{i})]$ denote the concatenation of estimated gradients. Instead of directly returning the estimated gradients for all agents trained by learner $j$, i.e., $\{\hat{\mathbf{e}}_{j,i}|\forall i\in[M],c_{j,i}\neq 0\}$, learner $j$ calculates a linear combination of the gradients: $y_{j}=\sum_{i=1}^{M}c_{j,i}\hat{\mathbf{e}}_{j,i}$ with weights provided by the assignment matrix $\mathbf{C}$ and returns $y_{j}$ back to the central controller.

At the central controller, let $\mathbf{y}_{\cal J}$ denote the results that have arrived by a certain time from learners ${\cal J}=\{j|y_{j}$ is received$\}$. Moreover, let $\mathbf{C}_{{\cal J}}\in\mathbb{R}^{|{\cal J}|\times M}$ be a submatrix of $\mathbf{C}$ formed by the $j$-th row of $\mathbf{C},\forall j\in{\cal J}$. The received gradients $\mathbf{y}_{\cal J}$ satisfy:

where $\mathbf{D}\in\mathbb{R}^{|{\cal J}|\times MN}$ is constructed as follows: for $i$-th row of $\mathbf{D}$, fill the $(1+({\cal J}_{i}-1)M)$-th to $({\cal J}_{i}M)$-th entries with $i$-th row of $\mathbf{C}_{{\cal J}}$ and set all other entries to 0, ${\cal J}_{i}$ denotes $i$-th element of ${\cal J}$. The vector $\mathbf{q}$ is a concatenation of all the gradients estimated by all learners. The central controller updates the agents’ parameters once it receives enough results to decode all estimated gradients, denoted as $\tilde{\mathbf{e}}$. This happens when $\operatorname*{rank}(\mathbf{C}_{\cal J})=M$, and the decoding equation is given as follows:

Alg. 1 summarizes the coded training procedure of DARL1N over a distributed computing architecture, referred to as the Coded DARL1N.

In Coded DARL1N, the gradients $\tilde{\mathbf{e}}$ used by the central controller for parameter updates are stochastic gradients computed by mini-batch samples, which are estimates of the true gradients $\mathbf{e}=[\mathbf{e}_{1},\ldots,\mathbf{e}_{M}]$, where $\mathbf{e}_{i}=[\nabla{\cal L}(\theta_{i}),\mathbf{g}(\phi_{i})]$ with ${\cal L}(\theta_{i})$ and $\mathbf{g}(\phi_{i})$ defined in (4) and (3), respectively. The estimation performance is illustrated in the following theorem.

Based on Theorem 4.4, we can infer that Coded DARL1N converges asymptotically similarly to other stochastic gradient descent-based methods [31].

The assignment matrix $\mathbf{C}$ affects both the policy variance and computational efficiency of Coded DARL1N. In this section, we explore different schemes, both uncoded and coded, for constructing the assignment matrix, and conduct theoretical analyses on their performance.

In this section, we evaluate the DARL1N algorithm and our coding schemes for mitigating compute stragglers.

In environments with local reward and transition models, DARL1N needs a suitably chosen distance metric to establish the agent neighborhoods that achieve the right balance between policy quality and ability to distribute the training efficiently. In future work, we will explore learning a neighbor distance metric that adapts to the environment, e.g., based on past episodes or contextual information, to achieve an effective balance between policy reward and training speed. Moreover, the coded distributed learning architecture for DARL1N is designed for a distributed computing system with a stable central controller in place. In future work, we will design a new coded architecture to improve resilience of central controllers such as introducing redundant central controllers using coding theory. Other issues to consider for further improvements include integration of curriculum learning similar as EPC, partially observable states, and software infrastructure to support distributed learning with low-latency communication.

This paper introduced DARL1N, a scalable MARL algorithm that can be trained over a distribute computing architecture. DARL1N reduces the representation complexity of the value and policy functions of each agent in a MARL problem by disregarding the influence of other agents that are not within one hop of a proximity graph. This model enables highly efficient distributed training, in which a compute node only needs data from an agent it is training and its potential one-hop neighbors. We conducted comprehensive experiments using five MARL environments and compared DARL1N with four state-of-the-art MARL algorithms. DARL1N generates equally good or even better policies in almost all scenarios with significantly higher training efficiency than benchmark methods, especially in large-scale problem settings. To improve the resilience of DARL1N to stragglers common in distributed computing systems, we developed coding schemes that assign each agent to multiple learners. We evaluate properties of MDS, Random Sparse, Repetition, LDGM codes and provide guidelines on selecting suitable assignment schemes under different situations.