Gossip-based Actor-Learner Architectures for Deep Reinforcement Learning

Multi-simulator training has contributed to the recent success of Deep Reinforcement Learning by stabilizing learning and allowing for higher training throughputs. We propose Gossip-based Actor-Learner Architectures (GALA) where several actor-learners (such as A2C agents) are organized in a peer-to-peer communication topology, and exchange information through asynchronous gossip in order to take advantage of a large number of distributed simulators. We prove that GALA agents remain within an epsilon-ball of one-another during training when using loosely coupled asynchronous communication. By reducing the amount of synchronization between agents, GALA is more computationally efficient and scalable compared to A2C, its fully-synchronous counterpart. GALA also outperforms A2C, being more robust and sample efficient. We show that we can run several loosely coupled GALA agents in parallel on a single GPU and achieve significantly higher hardware utilization and frame-rates than vanilla A2C at comparable power draws.


Introduction
Deep Reinforcement Learning (Deep RL) agents have reached superhuman performance in a few domains , Vinyals et al., 2019, but this is typically at significant computational expense [Tian et al., 2019]. To both reduce running time and stabilize training, current approaches rely on distributed computation wherein data is sampled from many parallel simulators distributed over parallel devices [Espeholt et al., 2018, Mnih et al., 2016. Despite the growing ubiquity of multi-simulator training, scaling Deep RL algorithms to a large number of simulators remains a challenging task.
On-policy approaches train a policy by using samples generated from that same policy, in which case data sampling (acting) is entangled with the training procedure (learning). To perform distributed training, these approaches usually introduce multiple learners with a shared policy, and multiple actors (each with its own simulator) associated to each learner. The shared policy can either be updated in a synchronous fashion (e.g., learners synchronize gradients before each optimization step [Stooke and Abbeel, 2018]), or in an asynchronous fashion [Mnih et al., 2016]. Both approaches have drawbacks: synchronous approaches suffer from straggler effects (bottlenecked by the slowest individual simulator), and therefore may not exhibit strong scaling efficiency; asynchronous methods are robust to stragglers, but prone to gradient staleness, and may become unstable with a large number of actors [Clemente et al., 2017].
in (1) and then proceed to optimize the policy using the policy gradient (PG) with the value function as a baseline: ∇ ω (− log π(a t |s t ; ω)A t ) , (2) where A t = G N t − V (s t ; θ t ) is the advantage function, which represents the relative value the current action has over the average. In order to both speed up training time and decorrelate observations, Mnih et al. [2016] collect samples and perform updates with several asynchronous actor-learners. Specifically, each worker i ∈ {1, 2, .., W }, where W is the number of parallel workers, collects samples according to its current version of the policy weights ω i , and computes updates via the standard actor-critic gradient defined in (2), with an additional entropy penalty term that prevents premature convergence to deterministic policies: ∇ ωi − log π(a t |s t ; ω i )A t − η a π(a|s t ; ω i ) log π(a|s t ; ω i ) . ( The workers then perform HOGWILD! [Recht et al., 2011] style updates (asynchronous writes) to a shared set of master weights before synchronizing their weights with the master's. More recently, Dhariwal et al. [2017] removed the asynchrony from A3C, referred to as A2C, by instead synchronously collecting transitions in parallel environments i ∈ {1, 2, .., W } and then performing a large batched update: π(a|s i t ; ω) log π(a|s i t ; ω) . (4) Gossip algorithms. Gossip algorithms are used to solve the distributed averaging problem. Suppose there are n agents connected in a peer-to-peer graph topology, each with parameter vector x (0) i ∈ R d . Let X (0) ∈ R n×d denote the row-wise concatenation of these vectors. The objective is to iteratively compute the average vector 1 i across all agents. Typical gossip iterations have the form X (k+1) = P (k) X (k) , where P (k) ∈ R n×n is referred to as the mixing matrix and defines the communication topology. This corresponds to the update x j for an agent v i . At an iteration k, an agent v i only needs to receive messages from other agents v j for which p (k) i,j = 0, so sparser matrices P (k) correspond to less communication and less synchronization between agents.
The mixing matrices P (k) are designed to be row stochastic (each entry is greater than or equal to zero, and each row sums to 1) so that lim K→∞ K k=0 P (k) = 1π , where π is the ergodic limit of the Markov chain defined by P (k) and 1 is a vector with all entries equal to 1 [Seneta, 1981]. 1 Consequently, the gossip iterations converge to a limit X (∞) = 1(π X (0) ); meaning the value at an agent i converges to x j . In particular, if the matrices P (k) are symmetric and doubly-stochastic (each row and each column must sum to 1), we obtain an algorithm such that π j = 1/n for all j, and therefore x (∞) i = 1/n n j=1 x (0) j converges to the average of the agents' initial vectors.
For the particular case of GALA, we only require the matrices P (k) to be row stochastic in order to show the -ball guarantees.

Gossip-based Actor-Learner Architectures
We consider the distributed RL setting where n agents (each composed of a single learner and several actors) collaborate to maximize the expected return V (s). Each agent v i has a parameterized policy network π(a t |s t ; ω i ) and value function V (s t ; θ i ). Let x i = (ω i , θ i ) denote agent v i 's complete set of trainable parameters. We consider the specific case where each v i corresponds to a single A2C agent, and the agents are configured in a directed and peer-to-peer communication topology defined by the mixing matrix P ∈ R n×n .
In order to maximize the expected reward, each GALA-A2C agent alternates between one local policygradient and TD update, and one iteration of asynchronous gossip with its peers. Pseudocode is 1 Assuming that information from every agent eventually reaches all other agents Algorithm 1 Gossip-based Actor-Learner Architectures for agent v i using A2C Require: Initialize trainable policy and critic parameters xi = (ωi, θi).
1: for t = 0, 1, 2, . . . do 2: Take N actions {at} according to πω i and store transitions {(st, at.rt, st+1)} 3: Compute returns G N t = N −1 i=0 γ i rt+i + γ N V (st+n; θi) and advantages At = G N t − V (st; θi) 4: Perform A2C optimization step on xi using TD in (1) and batched policy-gradient in (4) 5: Broadcast (non-blocking) new parameters xi to all out-peers in N out i 6: if Receive buffer contains a message mj from each in-peer vj in N in i then 7: Average parameters with messages 8: end if 9: end for 1 We set the non-zero mixing weights for agent vi to pi,j = denotes the set of agents that send messages to agent v i (in-peers), and N out i := {v j | p j,i > 0} the set of agents that v i sends messages to (outpeers). During the gossip phase, agents broadcast their parameters to their out-peers, asynchronously (i.e., don't wait for messages to reach their destination), and update their own parameters via a convex combination of all received messages. Agents broadcast new messages when old transmissions are completed and aggregate all received messages once they have received a message from each in-peer.
Note that the GALA agents use non-blocking communication, and therefore operate asynchronously. Local iteration counters may be out-of-sync, and physical message delays may result in agents incorporating outdated messages from their peers. One can algorithmically enforce an upper bound on the message staleness by having the agent block and wait for communication to complete if more than τ ≥ 0 local iterations have passed since the agent last received a message from its in-peers.
Theoretical -ball guarantees: Next we provide the -ball theoretical guarantees for the asynchronous GALA agents, proofs of which can be found in Appendix B. Let k ∈ N denote the global iteration counter, which increments whenever any agent (or subset of agents) completes an iteration of the loop defined in Algorithm 1. We define x (k) i ∈ R d as the value of agent v i 's trainable parameters at iteration k, and X (k) ∈ R n×d as the row-concatenation of these parameters.
For our theoretical guarantees we let the communication topologies be directed and time-varying graphs, and we do not make any assumptions about the base GALA learners. In particular, let the mapping ∈ R d characterize agent v i 's local training dynamics (i.e., agent v i optimizes its parameters by computing x i )), where α > 0 is a reference learning rate, and g (k) i ∈ R d can be any update vector. Lastly, let G (k) ∈ R n×d denote the row-concatenation of these update vectors. Proposition 1. For all k ≥ 0, it holds that where X (k+1) := 1n1 T n n X (k+1) denotes the average of the learners' parameters at iteration k + 1, and β ∈ [0, 1] is related to the joint spectral radius of the graph sequence defining the communication topology at each iteration.
Proposition 1 shows that the distance of a learners' parameters from consensus is bounded at each iteration. However, without additional assumptions on the communication topology, the constant β may equal 1, and the bound in Proposition 1 can be trivial. In the following proposition, we make sufficient assumptions with respect to the graph sequence that ensure β < 1. Proposition 2. Suppose there exists a finite integer B ≥ 0 such that the (potentially time-varying) graph sequence is B-strongly connected, and suppose that the upper bound τ on the message delays in Algorithm 1 is finite. If learners run Algorithm 1 from iteration 0 to k + 1, where k ≥ τ + B, then it holds that where β < 1 is related to the joint spectral radius of the graph sequence, α is the reference learning rate,β := β − τ +B τ +B+1 , and L := sup s=1,2,... G (s) denotes an upper bound on the magnitude of the local optimization updates during training.
Proposition 2 states that the agents' parameters are guaranteed to reside within an -ball of their average at all iterations k ≥ τ + B. The size of this ball is proportional to the reference learning-rate, the spectral radius of the graph topology, and the upper bound on the magnitude of the local gradient updates. One may also be able to control the constant L in practice since Deep RL agents are typically trained with some form of gradient clipping.

Related work
Several recent works have approached scaling up RL by using parallel environments. Mnih et al. [2016] used parallel asynchronous agents to perform HOGWILD! [Recht et al., 2011] style updates to a shared set of parameters. Dhariwal et al. [2017] proposed A2C, which maintains the parallel data collection, but performs updates synchronously, and found this to be more stable empirically. While A3C was originally designed as a purely CPU-based method, Babaeizadeh et al. [2017] proposed GA3C, a GPU implementation of the algorithm. Stooke and Abbeel [2018] also scaled up various RL algorithms by using significantly larger batch sizes and distributing computation onto several GPUs. Differently from those works, we propose the use of Gossip Algorithms to aggregate information between different agents and thus simulators. Nair et al. [2015], Horgan et al. [2018], Espeholt et al. [2018], Kapturowski et al. [2019], Gruslys et al. [2018] use parallel environments as well, but disentangle the data collection (actors) from the network updates (learners). This provides several computational benefits, including better hardware utilization and reduced straggler effects. By disentangling acting from learning these algorithms must use off-policy methods to handle learning from data that is not directly generated from the current policy (e.g., slightly older policies).
Gossip-based approaches have been extensively studied in the control-systems literature as a way to aggregate information for distributed optimization algorithms [Nedić et al., 2018]. In particular, recent works have proposed to combine gossip algorithms with stochastic gradient descent in order to train Deep Neural Networks [Lian et al., 2018, Assran et al., 2019, but unlike our work, focus only on the supervised classification paradigm.

Experiments
We evaluate GALA for training Deep RL agents on Atari-2600 games [Machado et al., 2018]. We focus on the same six games studied in Stooke and Abbeel [2018]. Unless otherwise-stated, all learning curves show averages over 10 random seeds with 95% confidence intervals shaded in. We follow the reproducibility checklist [Pineau, 2018], see Appendix A for details.
We compare A2C [Dhariwal et al., 2017], A3C [Mnih et al., 2016], IMPALA [Espeholt et al., 2018], and GALA-A2C. All methods are implemented in PyTorch [Paszke et al., 2017]. While A3C was originally proposed with CPU-based agents with 1-simulator per agent, Stooke and Abbeel [2018] propose a large-batch variant in which each agent manages 16-simulators and performs batched inference on a GPU. We found this large-batch variant to be more stable and computationally efficient (cf. Appendix C.1). We use the Stooke and Abbeel [2018] variant of A3C to provide a more competitive baseline. We parallelize A2C training via the canonical approach outlined in Stooke and Abbeel [2018], whereby individual A2C agents (running on potentially different devices), all average their gradients together before each update using the ALLREDUCE primitive. 2 For A2C and A3C we use the hyper-parameters suggested in Stooke and Abbeel [2018]. For IMPALA we use the hyperparameters suggested in Espeholt et al. [2018]. For GALA-A2C we use the same hyper-parameters as the original (non-gossip-based) method. All GALA agents are configured in a directed ring graph. All implementation details are described in Appendix C. For the IMPALA baseline, we use a prerelease of TorchBeast [Küttler et al., 2019] available at https://github.com/facebookresearch/torchbeast. Table 1: Across all training seeds we select the best final policy produced by each method at the end of training and evaluate it over 10 evaluation episodes (up to 30 no-ops at the start of the episode). Evaluation actions generated from arg max a π(a|s). The table depicts the mean and standard error across these 10 evaluation episodes. Convergence and stability: We begin by empirically studying the convergence and stability properties of A2C and GALA-A2C. Figure 1a depicts the percentage of successful runs (out of 10 trials) of standard policy-gradient A2C when we sweep the number of simulators across six different games. We define a run as successful if it achieves better than 50% of nominal 16-simulator A2C scores. When using A2C, we observe an identical trend across all games in which the number of successful runs decreases significantly as we increase the number of simulators. Note that the A2C batch size is proportional to the number of simulators, and when increasing the number of simulators we adjust the learning rate following the recommendation in Stooke and Abbeel [2018].
Figure 1a also depicts the percentage of successful runs when A2C agents communicate their parameters using gossip algorithms (GALA-A2C). In every simulator sweep across the six games (600 runs), the gossip-based architecture increases or maintains the percentage of successful runs relative to vanilla A2C, when using identical hyper-parameters. We hypothesize that exercising slightly different policies at each learner using gossip-algorithms can provide enough decorrelation in gradients to improve learning stability. We revisit this point later on (cf. Figure 3b). We note that Stooke and Abbeel [2018] find that stepping through a random number of uniform random actions at the start of training can partially mitigate this stability issue. We did not use this random start action mitigation in the reported experiments.
While Figure 1a shows that GALA can be used to stabilize multi-simulator A2C and increase the number of successfull runs, it does not directly say anything about the final performance of the learned models. Figures 1b and 1c show the rewards plotted against the number of environment steps when training with 64 simulators. Using gossip-based architectures stabilizes and maintains the peak performance and sample efficiency of A2C across all six games (Figure 1b), and also increases the number of convergent runs (Figure 1c).
Figures 1d and 1e compare the wall-clock time convergence of GALA-A2C to vanilla A2C. Not only is GALA-A2C more stable than A2C, but it also runs at a higher frame-rate by mitigating straggler effects. In particular, since GALA-A2C learners do not need to synchronize their gradients, each learner is free to run at its own rate without being hampered by variance in peer stepping times.
Comparison with distributed Deep RL approaches: Figure 1 also compares GALA-A2C to stateof-the-art methods like IMPALA and A3C. 3 In each game, the GALA-A2C learners exhibited good sample efficiency and computational efficiency, and achieved highly competitive final game scores. Next we evaluate the final policies produced by each method at the end of training. After training across 10 different seeds, we are left with 10 distinct policies per method. We select the best final policy and evaluate it over 10 evaluation episodes, with actions generated from arg max a π(a|s).
In almost every single game, the GALA-A2C learners achieved the highest evaluation scores of any method. Notably, the GALA-A2C learners that were trained for 25M steps achieved (and in most cases surpassed) the scores for IMPALA learners trained for 50M steps [Espeholt et al., 2018].       Figure 2: (a) The radius of the -ball within which the agents' parameters reside during training. The theoretical upper bound in Proposition 1 is explicitly calculated and compared to the true empirical quantity. The bound in Proposition 1 is remarkably tight. (b) Average correlation between agents' gradients during training (darker colors depict low correlation and lighter colors depict higher correlations). Neighbours in the GALA-A2C topology are annotated with the label "peer." The GALA-A2C heatmap is generally much darker than the A2C heatmap, indicating that GALA-A2C agents produce more diverse gradients with significantly less correlation. Bubble sizes indicate frame-rates obtained by the corresponding algorithms; larger bubbles depict higher frame-rates. GALA-A2C achieves higher hardware utilization than A2C at comparable power draws. This translates to much higher frame-rates and increased energy efficiency. (b) Hardware utilization/energy efficiency vs. number of simulators. GALA-A2C benefits from increased parallelism and achieves a 10-fold improvement in GPU utilization over A2C.

Effects of gossip:
To better understand the stabilizing effects of GALA, we evaluate the diversity in learner policies during training. Figure 2a shows the distance of the agents' parameters from consensus throughout training. The theoretical upper bound in Proposition 1 is also explicitly calculated and plotted in Figure 2a. As expected, the learner policies remain within an -ball of one-another in weight-space, and this size of this ball is remarkably well predicted by Proposition 1.
Next, we measure the diversity in the agents' gradients. We hypothesize that the -diversity in the policies predicted by Proposition 1, and empirically observed in Figure 2a, may lead to less correlation in the agents' gradients. The categorical heatmap in Figure 2b shows the pair-wise cosine-similarity between agents' gradients throughout training, computed after every 500 local environment steps, and averaged over the first 10M training steps. Dark colors depict low correlations and light colors depict high correlations. We observe that GALA-A2C agents exhibited less gradient correlations than A2C agents. Interestingly, we also observe that GALA-A2C agents' gradients are more correlated with those of peers that they explicitly communicate with (graph neighbours), and less correlated with those of agents that they do not explicitly communicate with.
Computational performance: Figure 3 showcases the hardware utilization and energy efficiency of GALA-A2C compared to A2C as we increase the number of simulators. Specifically, Figure 3a shows that GALA-A2C achieves significantly higher hardware utilization than vanilla A2C at comparable power draws. This translates to much higher frame-rates and increased energy efficiency. Figure 3b shows that GALA-A2C is also better able to leverage increased parallelism and achieves a 10-fold improvement in GPU utilization over vanilla A2C. Once again, the improved hardware utilization and frame-rates translate to increased energy efficiency. In particular, GALA-A2C steps through roughly 20 thousand more frames per Kilojoule than vanilla A2C. Figures 1f and 1g compare game scores as a function of energy utilization in Kilojoules. GALA-A2C is distinctly more energy efficient than the other methods, achieving higher game scores with less energy utilization.

Conclusion
We propose Gossip-based Actor-Learner Architectures (GALA) for accelerating Deep Reinforcement Learning by leveraging parallel actor-learners that exchange information through asynchronous gossip. We prove that the GALA agents' policies are guaranteed to remain within an -ball during training, and verify this empirically as well. We evaluated our approach on six Atari games, and find that GALA-A2C improves the computational efficiency of A2C, while also providing extra stability and robustness by decorrelating gradients. GALA-A2C also achieves significantly higher hardware utilization than vanilla A2C at comparable power draws, and is competitive with state-of-the-art methods like A3C and IMPALA. github.com/openai/gym • An explanation of how samples were allocated for training / validation / testing. We didn't use explicit training / validation/ testing splits -but ran each algorithm with 10 different random seeds. • An explanation of any data that were excluded. We only used 6 atari games due to time constraints -the same 6 games that were used in Stooke and Abbeel [2018]. • The range of hyper-parameters considered, method to select the best hyper-parameter configuration, and specification of all hyper-parameters used to generate results. We used standard hyper-parameters from Dhariwal et al. [2017], Stooke and Abbeel [2018], Espeholt et al. [2018]. • The exact number of evaluation runs. We used 10 seeds for the Atari experiments.
• A description of how experiments were run. See Appendix C for full details.
• A clear definition of the specific measure or statistics used to report results. 95% confidence intervals are used in all plots / tables unless otherwise stated. • Clearly defined error bars. 95% confidence intervals are used in all plots / tables unless otherwise stated. • A description of results with central tendency (e.g. mean) and variation (e.g. stddev).
95% confidence intervals are used in all plots / tables unless otherwise stated. • A description of the computing infrastructure used. See Appendix C for full details.

B Proofs
Setting and Notation Before presenting the theoretical guarantees, we define some notation. Suppose we have n learners (e.g., actor-critic agents) configured in a peer-to-peer communication topology represented by a directed and potentially time-varying graph (the non-zero entries in the mixing matrix P (k) define the communication topology at each iteration k).
Learners constitute vertices in the graph, denoted by v i for all i ∈ [n] , and edges constitute directed communication links. Let N out i denote agent v i 's out-peers, the set of agents that v i can send messages to, and let N in i denote agent v i 's in-peers, the set of agents that can send messages to v i . If the graph is time-varying, these sets are annotated with time indices. Let x i ∈ R d denote the agent v i 's complete set of trainable parameters, and let the training function T i : R d → R d define agent v i 's training dynamics (i.e., agent v i optimizes its parameters by iteratively computing x i ← T i (x i )).
For each agent v i we define send-and receive-buffers, B i and R i respectively, which are used by the underlying communication system (standard in the gossip literature [Tsitsiklis et al., 1986]). When an agent wishes to broadcast a message to its out-peers, it simply copies the message into its broadcast buffer. Similarly, when agent receives a message, it is automatically copied into the receive buffer. For convenience, we assume that each learner v i can hold at most one message from in-peer v j in its receive buffer, R i at any time k; i.e., a newly received message from agent v j overwrites the older one in the receive buffer.
Let k ∈ N denote the global iteration counter. That is, k increments whenever any agent (or subset of agents) completes one loop in Algorithm 1. Consequently, at each global iteration k, there is a set of agents I that are activated, and within this set there is a (possibly non-empty) subset of agents C ⊆ I that gossip in the same iteration. If a message from agent v j is received by agent v i at time k, let τ (k) j,i denote the time at which this message was sent. Let τ ≥ τ (k) j,i for all i, j ∈ [n] and k > 0 denote an upper bound on the message delays. For analysis purposes, messages are sent with an effective delay such that they arrive right when the agent is ready to process the messages. That is, a message that is sent by agent v j at iteration k and processed by agent v i at iteration k, where k ≥ k , is treated as having experienced a delay τ (k) j,i = k − k , even if the message actually arrives before iteration k and waits in the receive-buffer.
Let αg denote agent v i 's local computation update at iteration k after scaling by some reference learning rate α > 0, and define g (k) i := 0 if agent v i is not active at iteration k. Algorithm 1 can thus be written as follows. If agent v i does not gossip at iteration k, then its update is simply x (5) If agent v i does gossip at iteration k, then its update is where x τ (k) j,i j is the parameter value of the agent v j , at the time where the message was sent, i.e., τ j,i .
We can analyze Algorithm 1 in matrix form by stacking all n agents' parameters, x (k) i ∈ R d , into a matrix X (k) , and equivalently stacking all of the update vectors, g (k) i ∈ R d , into a matrix G (k) . In order to represent the state of messages that are in transit (sent but not yet received), for analysis purposes, we augment the graph topology with virtual nodes using a standard graph augmentation [Hadjicostis and Charalambous, 2013] (we add τ virtual nodes for each non-virtual agent, where each virtual node stores a learner's parameters at a specific point within the last τ iterations). Letñ := n(τ + 1) denote the cardinality of the augmented graph's vertex set. Equation (6) can be re-written as where X (k) , G (k) ∈ Rñ ×d , and the mixing matrixP (k) ∈ Rñ ×ñ corresponding to the augmented graph is row-stochastic for all iterations k, i.e., all entries are non-negative, and all rows sum to 1 . Mapping (6) to (7) may not be obvious, but is quite standard in the recent literature. We refer the interested reader to Assran and Rabbat [2018], Hadjicostis and Charalambous [2013].
Proof of Proposition 1. The proof is very similar to the proofs in Assran et al. [2019] and Assran and Rabbat [2018], and makes use of the graph augmentations in Hadjicostis and Charalambous [2013], the lower dimensional stochastic matrix dynamics in Blondel et al. [2005], and the ergodic matrix results in Wolfowitz [1963]. Since the matricesP (k) are row-stochastic, their largest singular value is 1, which corresponds to singular vectors in span {1ñ}. Let the matrix Q ∈ R (ñ−1)×ñ define an orthogonal projection onto the space orthogonal to span {1ñ}. Associated to each matrix   [Stooke and Abbeel, 2018] to original A3C [Mnih et al., 2016]. Running A3C with larger-batches provides more stable and sample efficient convergence (top row), while also maintaining computational efficiency by leveraging GPU acceleration (bottom row). .99 Max number of no-ops at the start of the episode 30 Table 2: Hyperparameters for both A2C, GALA-A2C, and A3C v 1 v 2 · · · v n−1 v n Figure 5: Example of an n-agents/1-peer ring communication topology used in our experiment