extfieldsofstudy:
Computer Science
Mathematics

text:
Function Naming in Stripped Binaries Using Neural Networks

In this paper we investigate the problem of automatically naming pieces of assembly code. Where by naming we mean assigning to portion of code the string of words that would be likely assigned by an human reverse engineer. We precisely define the framework in which our investigation takes place. That is we define problem, we provide reasonable justifications for the choice that we made during our designing of the training and test steps and we performed a statistical analysis of function names in a large real-world corpora of over 4 millions of functions. In such framework we test several baselines coming from the field of NLP.

I. INTRODUCTION
Last few years have witnessed the growth of a trend consisting in the application of machine learning (ML) and natural language processing (NLP) techniques to the code, as illustrated in [14]. In fact, the vast and increasing amount of high quality software available through open source repositories such as GitHub, has given the chance to leverage such large amount of source code as a ground truth for building statistical models of code. The design choice of using ML to build code models is motivated by the naturalness hypothesis which underlines the similarities between programming languages and human languages. According to this hypothesis, software is a form of human communication with similar statistical properties to natural language and these properties can be exploited to build better software engineering tools [14]. The practice of applying ML and NLP techniques to the code turned out to be very helpful and effective in many tasks such as predicting program bugs, predicting program behavior, automatically creating new code, predicting identifier names, translating code between programming languages, etc. Thus, the success given by the application of NLP techniques to source code has led to investigate the possible use of such techniques also in the context of binary code.
Following this research line, in this paper we investigate the feasibility of using the same techniques to predict the name of functions in stripped binary programs. The latter are binary executable files that only contain low-level information such as instructions, registers and memory addresses but no debug symbols since they are not directly necessary for program execution. Debug symbols are generated by compiler programs on the basis of the source code and typically include information about functions and variables, such as name, location, type and size which is helpful for debugging and security analysis of a binary. Being non essential for the software execution, symbols are often removed from a program after compilation, increasing the complexity of reverse engineer the software.
Reconstructing symbols in a binary program can be a very useful feature for all those field where reverse engineering code plays a crucial role, e.g. malware analysis. Usually, after having disassembled the malware a reverse engineer starts analyzing the set of assembly instructions of the program looking for specific functions (e.g. encryption or network) that might reveal the malicious nature of the software. This task could be daunting, especially when the binary code is stripped, since function names are simply represented by debug symbols with no semantic information. In this case, it could be very helpful having explanatory names for such functions, as they would save a lot of effort to the reverser.
Recently, a few works proposed solutions to this problem. For example, [7] and [4] show that this problem can be solved predicting directly the full name of a function or generating its name looking only at the calls made by a function. However, the problem at hand is far from being solved, for several reasons: • existing solutions work only under strong assumption, like the presence of calls to dynamically linked libraries in each functions, or a closed set of possible assignable names to predict from; • the evaluation of these solutions has been performed on small datasets that contain binary programs with little variance; • there is no public and common dataset to compare existing solutions. Starting from these issues in this paper we propose the following contributions: • we provide a general definition of the problem; • we describe a new dataset with a large variance of real world binaries; • We test different Deep Neural Network architectures that works in the general setting of the problem and do not require any underlying assumption. After this introduction, Section II discussed the state of the art, Section III introduces the function naming problem, Section IV describes the dataset used for the evaluation, Section V details the proposed solution and Section VI reports the experimental results. Finally, Section VII concludes the paper.

A. Debug symbols prediction
Predicting debugging symbols, including function names, through ML is a rather new field of research with few contributions. The most notable work in this area is DEBIN, proposed by He et al. [7]. DEBIN use conditional random fields to predict function names, variable names and types. Differently from out work, DEBIN assigns to function only names that are already known to be function names, i.e. it cannot generalize and generate new names. This limitation is surpassed by NERO [4], which models the problem of predicting function names as a neural machine translation (NMT) task where each function is represented by a set of call sites sequences, that retain information about the names of dynamically linked functions.
Finally, DIRE [11] proposes a probabilistic technique for variable name recovery that uses both lexical and structural information recovered by the decompiler. DIRE uses the extended context provided by the decompilers internal abstract syntax tree (AST) representation of the decompiled binary, which encodes additional structural information, to train it neural network.

B. Deep Learning for Binary Analysis
Recently a lot of works focussed on the usage of deep learning techniques applied to the binary similarity problem. Given two binary functions, the binary similarity problem consists in determining whether such functions are the result of differently compiling the same source code. This problem is related to the one addressed in this paper in the sense that, the problem of predicting function names from stripped binaries, could also be seen as, first cluster similar functions, and then assign similar names to such similar functions. A few works propose to use embeddings to represent binary code in a ndimensional numeric space while translating code similarity to euclidean vicinity.
GEMINI [17] and SAFE [16] both make use of graph embedding networks to compute functions embeddings. In particular, they build the control flow graph (CFG) of each function and then use the structure2vec graph embedding technique to translate the CFG to a vector of real numbers. The difference between these two works resides in the way features are extracted from the CFG: GEMINI manually-selects such features, whereas SAFE uses an unsupervised feature learning mechanism.
It is worth pointing out the strong similarity between the SAFE architecture, used to calculate functions embeddings, and the encoder of the architecture which is used in this paper to accomplish the task of predicting function names. Moreover, SAFE employs an instructions embedding technique to map assembly instructions to vectors; the same embeddings are used to feed the networks proposed in this work as well.
Recently, Ding et al. [5] proposed a function embedding solution called Asm2Vec. This solution is based on the PV-DM model [12] for NLP. Operatively, Asm2Vec computes the CFG of a function, and then it performs a series of random walks on top of it. Asm2Vec outperforms several state-ofthe-art solutions in the field of binary similarity; however, its applicability is limited by the fact that it requires libc call symbols to be present in the binary code as tokens to produce the embedding of a function and, furthermore, it cannot generate cross-platform embeddings.
The binary similarity problem has also been applied to solve different problems. Katz et al. [9] proposed an approach to binary software decompilation based on neural machine translation [8]. Their solution applies an NMT model to small snippets of canonical binary code to translate it to an intermediate code representation that are then transformed in C code using templates. More recently Fu et al. [6] proposed a new framework for solving this problem called Coda. While not directly linked to the function naming problem, binary code decompilation still represent a fundamental and orthogonal approach to reverse engineer software.

III. PROBLEM DEFINITION
We are interested in exploring solutions for the function naming problem. That is, given a binary code b, representing a functional unit of code 1 , we want to output a string s which represents a "meaningful" name for b, that is a name that represents its semantic and its role inside a binary.
The above problem is really challenging, and by its nature it cannot be defined more precisely without incurring in complex reasoning about what the "semantic" of code is. a) Training: Statistical learning methods are especially suitable for problems with fuzzy definitions. However, in order for these methods to be effective, their models need to be trained and tested on a suitable dataset. Such a dataset must have a reasonably large size (millions of functions), contain the functions binary code and their names.
Function names will be used to train statistical models, thus their content is crucial for the trained models to correctly embed the function semantics. In particular we assume that programmers, when writing code in an high-level language, assigns names to functions that include information about the function semantics and their context of execution. The above assumption does not always hold true. However, we find reasonable to assume that it holds most of the time, especially in large projects developed by professional or skilled programmers that follow common function naming conventions 2 . This assumption allows us to create a reference dataset (described in Section IV) for our problem by disassembling the binary code of large open source projects. b) Testing: There is an unavoidable ambiguity in the output of any method that names something. This is due to the fact that several different meaningful descriptive names can be associated to a certain function of code. As an example, a function implementing quick sort on an array can be named "Quick-sort", "quick-array-sort", "sort", etc. This creates a problem in the way any solution is tested: in order to evaluate its accuracy we should consider all possible meaningful names. This is again unfeasible, and we will test our method on a partition of the dataset above mentioned. We will say that a prediction is correct if is the name present in the dataset, other predictions will be deemed as wrong even if they could be meaningful.
c) Vocabulary and restricted names: Unfortunately, we found that functions names in our dataset are noisy, e.g. many functions of the OpenGL library contain the bigram "gl". Such pattern is recurrent in many libraries and software, as developers use words and acronyms that have a meaning in the software itself, but that do not add much to the semantic of the function. In order to clean our dataset we designed a filtering process (described in a detailed way in Section V). This filtering process has the purpose of associating each original name to a reduced name over a restricted vocabulary of words. We found that such restriction preserves part of the semantic of the majority of names in our dataset while it solves the problem described above. d) Simplifying assumptions: Apart from restricting the vocabulary (and thus the set of possible names) we perform an additional assumption. We transform our problem from the one of predicting a string, and thus a sequence of words, to the one of predicting a set of words. More clearly, if the actual name of the function is "open file" our goal is to predict the set {open, file}. This simplifying assumption allows us to threat the problem with several deep learning techniques. Not only the ones born for predicting sequences (such as the notorious Seq2Seq), but also those developed for multi-labels classification. The tokens in the vocabulary are the labels, and predicting a set of tokens for a function is equivalent to classifying it with multiple possible labels.

IV. DATASET
In this section we describe the dataset used in the experiments.

A. Executable Sources
The dataset has been obtained crawling all available packages from Ubuntu apt repository , collecting 22040 packages. Executables inside packages have been disassembled using IDA Pro, we successfully disassembled 119504 distinct ELF files. Finally, we discarded all executables without debug symbols and we filtered duplicate functions. At the end of this process we obtained 5470954 named functions.

B. Functions processing and Filtering
One straightforward representation for a binary function is the control flow graph (CFG). However, this type of function representation to use as input for deep learning network has been shown to produce less accurate results [15] based on this observation we decided to follow the success of several recent works like [16] and [5] that represent functions as an ordered list of instructions. The order is given by the address of each instruction inside the program. The average number of instructions per function is 159.12, we set a maximum length of 500 instructions per function and we truncate functions longer than this threshold.

C. Name Preprocessing and Filtering
After collecting the dataset we apply a normalization process to function names. Often names are modified by the compiler that encodes several information to enforce their uniqueness; this operation is usually called name mangling. Furthermore, differently from natural language, function names do not contain blank spaces, this makes much more difficult splitting them in tokens. Starting from this observation we preprocess and filter function names in five steps: demangling, function name splitting, stemming, tokens selection and outof-vocabulary tokens removal. a) Demangling: : The aim of this step is to first remove the encoding added by the compiler. Since compilers perform mangling in a standard way, it is possible to perform name demangling using standard libraries. During this step we also filtered all the functions obtained by binaries not written in C/C++ (e.g. code written in GO, Haskell, etc.). b) Function name splitting: : This step consists in splitting function names into tokens. This is achieved by using the natural partition provided by camel and snake notations, which are generally adopted for function names. c) Stemming: : this is a technique used in information retrieval to reduce inflected (or sometimes derived) words to their base form. Nevertheless, such technique turns out to be very useful in this context, since it has the effect of reducing the vocabulary of function name tokens by mapping different forms of the same token into a unique one (for example the tokens "shared" and "sharing" are both mapped to their base form "share"). Stemming is important since it is not necessary for the network to learn the syntactically correct token to associate to each function, but rather the semantically correct one. d) Tokens Selection: : the last step consists in selecting only a given amount of tokens as vocabulary. This operation has the goal of removing useless and meaningless tokens from function names that could insert noise during the learning process. The token selection process consists first in assigning a score to each token and then extracting the top n tokens with the highest score (the chosen value for n is 1000). These top n tokens are used as the vocabulary of function name tokens. The score for each token t was calculated with: Where i is an index over all the packages in the dataset and delta(i, t) is equal to 1 if the token t in the i package, otherwise 0. This choice permit us to exclude tokens that appear only in few packages independently from the frequency of the token inside the package. In this way we avoid to assign an high score to tokens that are not semantically relevant. e) OOV Removal and final filtering: The fifth and final step consists in removing from function names all those tokens not contained in the vocabulary retrieved in the previous step. There are few cases in which function names only consists of out-of-vocabulary tokens resulting in an empty name; in such cases functions are removed from the dataset. After applying this last step to our dataset we remove 13% of functions.

D. Data Splitting
In order to train and evaluate the naming models we need to split the dataset in the canonical three sets: Train, Validation and Test. In order to avoid information leakage from the training set to the validation or test we split the functions in our dataset according the packages: all functions from a given package belong to one of the three sets. We put 80% of functions in the training set, 10% in the validation set and the 10% in the set test.
V. SOLUTION OVERVIEW Sequential based solutions are usually used for NLP problems like Machine-Translation or Question Answering. This models are able to takes a sequence as input and to output another sequence. We used this architecture for our experiments since translation problems look very similar to function naming except for the fact that output sequences can be very shorter with respect to the input.
The sequence-to-sequence network (Seq2Seq) is also called encoder-decoder network, since it consists of two Recurrent Neural Networks (RNNs) called encoder and decoder. The encoder takes as input the list of assembly instructions and encodes its information into a set of vectors, whereas the decoder predicts the function name by decoding this information.
The encoder consists of a bidirectional RNN with Longshort term memory (LSTM) cells. The use of a bidirectional encoder is important since it allows to compute for each instruction its hidden states vector that takes into account the instruction itself and its previous and following context.
The decoder is a forward RNN that starts taking as input the last hidden state of the encoder and the attention matrix. At each time step i the i th hidden state of the decoder is passed through a softmax layer that outputs the probability distribution of all tokens over the target vocabulary. From this probability distribution it is possible to choose the i th token of the function name. The attention mechanism allows to better model long distance dependencies which are a critical aspect in assembly code. In fact, the attention decoder, while generating function name tokens, is able to understand which part of the context actually matters. Moreover, the attention decoder does not work with a unique vector of fixed size that "squashes" all the information regarding the input assembly instruction sequence as traditional encoder-decoder network does. Indeed, it keeps around vectors for each assembly instruction, and then references these vectors at each decoding step. One common strategy to choose the next token from the probabilistic output of the decoder is beam-search. This method permits to predict k sequences: at each time it explores the output distribution to find an approximation of the sequence that maximizes the full sequence probability.

A. Methodology
The implementation of the Seq2Seq network used for the experiments, is the one provided in [3], whereas the used implementation of the transformer network is [2]. The tool used to disassemble binaries is IDA Pro. Token stemming was implemented using the TreeTagger Python library [10], whereas function name demangling was implemented with cxxfilt [1].
In order to speed up the evaluation phases performed during the training process, the validation set has been reduced by randomly selecting 50000 functions. Parameters have been tuned on the validation set, whereas the final model has been evaluated on the test set. Early stopping has been used to stop training at the point when performance on the validation set starts degrading or stops improving. The metric used for stopping the training was ROUGE-1 [13] instead of the loss function of the validation set, since the former does not take into account the order of tokens, whereas the latter does. Decoding of test set has always been carried out using beamwidth 5.
The limit on 500 instructions as the maximum function length ensures that only˜6% of instructions sequences in the multiple compilers in the Ubuntu dataset were sliced. All the other instruction sequences were considered by the network in their entirety.
Regarding the Seq2Seq training process, experiments used the following set of parameters: All the details about the dataset and parameters used to train this model are described in [16]. The network was also tested with no pre-trained embeddings.
In order to train the Seq2Seq network, pre-trained instruction embeddings have been used. Such embeddings are computed using the i2v model also employed in SAFE. All the details about the dataset and parameters used to train this model are provided in [16]. The network was also tested with no pre-trained instruction embeddings. In this case embeddings for single instructions were randomly initialized and trained together with the network itself.

B. Results
Performance of the two Seq2Seq networks, with and without pre-trained instruction embeddings, were evaluated calculating precision, recall and F1-score of the predicted tokens. Table  I reports the results. The performance obtained wioth the Seq2Seq network with pre-trained embeddings are close to the ones achieved with the LSTM-text configuration in [4]. The main difference between the configuration used in this experiment and LSTM-text lies in the input given to the Seq2Seq network: LSTM-text feeds the network with assembly code tokens, whereas in this experiment the network receives entire assembly instructions as input. The problem with LSTM-text is that, considering separate assembly code tokens, inevitably leads to extremely long input sequences (nearly three times the length of sequences with whole assembly instructions). Therefore, in order to prevent the network from slicing the assembly code sequences of too many functions, it is necessary to increase the maximum source sequence length parameter, leading to a very slow training.
To better understand the quality of the obtained results, performance have been compared to those achievable by a random predictor. The random prediction has been created by using the same probability distribution of function name lengths as the one of the original function names in the test set and by randomly assigning tokens to each function. As can be noticed from the table, results achieved by the model are clearly better than those achieved by a random prediction. This result suggests that even if this model does not provide strong performance overall, there are functions for which it is able to understand behaviors and assign correct tokens.
Regarding the performance difference between the two Seq2Seq networks, the 1%-2% advantage obtainable by using pre-trained instruction embeddings is coherent with the results reported in [16].

VII. CONCLUSION
This paper introduces a solution for the problem of assigning names to functions in stripped binary code that is based on the usage of a Seq2Seq network architecture borrowed from the Machine-Translation research field.
The solution was tested on a new dataset consisting of 5470954 functions extracted from 22040 packages in the Ubuntu apt repository. Experimental results show some initial positive findings: the network is able to predict correct tokens for some functions, providing an interesting context help for reverse engineers. However, good predictions are restricted to a limited number of cases, while overall performance are still limited.


Pattern recognition of UAV flight data based on semi-supervised clustering

UAV is an unmanned aerial vehicle controlled by a remote radio signal or a trajectory planning software carried itself. It is widely used in military, civil and scientific research fields. However, due to the lack of real-time decision-making ability, the UAV has high fault rate. The flight quality assessment of UAV and the construction of fault prediction model can be used for debugging and fault-removing to customer’s aircraft, and also to increase the added value of the civilian UAV products. Before building a fault prediction model, a very important step is to identify the pattern of sampled data. For each group of flight data, the efficiency and accuracy rate of manual quality evaluation and fault identification are not acceptable. Based on the UAV flight data accumulated in the big data platform of an UAV production company in Shenyang, Liaoning Province of China, this paper proposes a semi-supervised clustering technique to do automatic pattern recognition for the sampling points. According to the characteristics of UAV flight data, two different methods are designed to choose initial centroids. Meanwhile, we use the existing normal flight data to train distance thresholds to combine some clusters to eliminate the resulting error clustering. Real flight data or flight test data with manually added labels are used to run the proposed algorithms to verify the recognition results. The experimental results show that the proposed methods greatly improve the efficiency and accuracy of adding precise labels to the historical flight data and play a role in assisting the manual recognition of sampling points while strengthening the management and statistics.

Introduction
The unmanned aerial vehicle (UAV) has a significant improvement in its autonomous ability compared with the manned vehicle, and the ability to survive is greatly strengthened. The UAV can replace humans to complete the task in a bad environment and do not need to worry about the safety of the driver's life, and can perform the task of high risk [1,2,3,4]. So, UAV has been widely applied in military, civilian and scientific research fields. The widely application of UAV requires that it should have a high stability in addition to the efficient completion of the task, that is, the UAV is required to  2 detect the health status of itself and take the corresponding scheme according to the current state [5]. Due to the lack of real-time decision-making ability, the UAV has high fault rate. Fault prediction is the core of UAV health management technology. The flight quality assessment of UAV and the construction of fault prediction model can be used for debugging and fault-removing to customer's aircraft, and also to improve the added value of the civilian UAV products. The methods of fault diagnosis can be divided into model-based and model-free methods. When the model is not accurate, the diagnostic accuracy of the model-based diagnosis method is low, so the diagnosis method that does not rely on the model is getting more and more attention. The advantage of the model-free method is that it does not require the accurate model of the system and has strong self-adaption ability. Its defects are complex construction making it not conducive to practical application [6]. The model-free methods can be classified into data driven, knowledge based and discrete event-based methods. UAV produces a large number of real-time data during the flight process. Using these data and machine learning algorithms, such as neural network-based methods [7,8,9,10], the fault prediction model of aircrafts can be constructed. However, the real-time data produced in the flight process are all unlabelled data, which is not to determine which sampling points in a flight data are fault-free points of normal flight and which are the fault points. So before building a fault prediction model, a very important step is to identify the pattern of the sampling data, which is also partially for improving the whole flight portrait. The interval of sampling points for UAV flight data is usually in milliseconds, for example, the data involved in this paper comes from the big data platform of a Shenyang UAV production company, with the data sampling interval of 2ms. For each group of flight data, the efficiency and accuracy rate of manual quality evaluation and fault identification are not acceptable. All measurement variables have strong correlations, rather than independent characteristics. Therefore, we speculate that the pattern between the variables in normal flight will be different from that after fault happens. Running the proposed clustering methods on one group of flight data, the patterns of the sampling points are distinguished. In this algorithm, two different methods of choosing initial centroids are designed according to the characteristics of UAV flight data. Meanwhile, we use the existing normal flight data to train distance thresholds to combine some clusters to eliminate the resulting error clustering. We use real flight data or flight test data to test our methods. The experimental results show that the proposed methods greatly improve the efficiency and accuracy of adding precise labels to the historical flight data and play a role in assisting the manual recognition of sampling points while strengthening the management and statistics.

Feature selection
The UAV system consists of the controlled object (aircraft), the controller (generally including the measuring element, the sensor) and the actuator (steering engine, propeller). In addition, some other auxiliary positioning components (such as millimeter wave radar) may also be installed on the basis of the specific circumstances. The flight state of the aircraft is automatically determined by the flight control system according to the height or vertical speed of the aircraft. The flight mode of the aircraft can be controlled by the remote controller. The control volume of the remote controller channel is different under different flight modes. According to the flight mode and control volume or certain mission planning, the flight control system calculates the expectation data of location and speed. The controller calculates some control quantities based on these control expectations and current aircraft status and drives the actuator to control the behaviour of the important components, such as accelerometers, gyroscopes, magnetic compass and other ones, so that the aircraft will produce a certain mode of motion. The flight sensors mounted on these components measure these movements, including the pitch angle, the roll angle, the corresponding angular velocity and other variables, and return the calculated values, and the barometer returns the measured height. These values as actual values are compared with expectation values, and some control quantities for adjusting attitude are obtained, and then, the flight is corrected. Therefore, we can filter out the data generated during the The UAV flight control system adopts closed loop control. In different flight modes, the variables involved in the control and calculation are different. There are more than one flight mode switching in one flight data. Therefore, the unified characteristic variables cannot be used. For example, for multi axis UAV, in attitude mode, the index of speed is not involved in calculation and control. For the helicopter's unique mode of non-aileron, the indices of attitude, position and speed can be eliminated. Therefore, this paper runs clustering algorithm respectively on different flight modes.

Data normalization
After manual screening, we have retained a total of 51 characteristic variables for the flight data obtained by the big data platform, all of which are numerical data. Because the range gap between the feature variables is large and the value of each characteristic variable tends to be concentrated, the linear normalization function (Min-Max Scaling) is adopted to convert the original data value to the value in range of [-1,1]: 2.3. Feature merging and feature weighting 2.3.1. Feature merging. Abrupt separation of three axis posture is one common fault which will produce the poor following values of Pitch, Roll and Yaw. According to this, we get the new combination features through the difference between the expectation value and the measure value of Pitch, Roll and Yaw.

Feature weighting.
Another common fault is sensor failure. Data show that about 50% of UAV faults are caused by sensor failures [11]. When the fault is identified manually, it is found that the three-axis data change returned by the accelerometer is the most dominant fault data, which generally indicates that the accelerometer vibration suddenly becomes larger and is the most frequent fault type. Data normalization eliminates the influence of eigenvalues on distance calculation results, thus weakening the change of this mode. We dynamically weighted two sets of three axis data returned by the accelerometer (one set is the fixed data, the other is the shock absorption data), that is, the greater the three axis values of a certain sampling point being higher than its previous sampling point, the higher the weight value added to it.
The weight function is , in which, ' ' represents Euclidean distance function, is the vector composed of the two sets of three axis data. If there is a fault, the acceleration value will change greatly, and the corresponding weight of the point will be bigger. However, this does not distinguish between a real fault and a sharp change in the acceleration caused by the unsuitable operation of human operator, so that these will also be classified as fault data.

Choose the number of clusters
For simplification, we only consider one kind of fault in flight process, or a most significant fault mode, not considering the mode of multiple fault superpositions for now. In fact, through the analysis of the flight data, we find that in the actual flight process, there are few fault superimpositions, even if there is, it is also such a situation that a component fault happens first, and before a short time of crashing, or in the moment of crashing, there may appear several other faults. After fault happens, there are two cases of crashing and non-crashing for the aircraft. We hope to identify the normal flight data points, the fault points (if crashing, also containing the crashing point), and the points after crashing (if crashing). Therefore, the selected number of clusters is 2 (not crashing) and 3 (crashing For the flight data without fault, we pre-train cluster centroids distance threshold, and two clusters with the inter centroid distance less than the threshold are considered to be an error pattern recognition. For example, for a group of flight data without fault, all of the sampling points in theory should belong to the same cluster, but because the minimum clustering number is 2, the clustering results are not reasonable. At this time, the distance between the two cluster centroids is smaller than that of the faultfree points cluster and the fault points cluster and so, we will merge the two clusters.

Choose the initial centroids
We design two methods to choose the initial centroids and run the proposed clustering algorithm respectively: (1) Random selection of k sampling points as the initial centroids; (2) The two adjacent sampling points with the maximum change amplitude of the three axis acceleration values are selected as the first two initial centroids, and the farthest sampling point from the set of the first two initial centroids is selected as the third centroid.
The third centroid in the method (2) determines which is farthest from set S (here composed of the first two initial centroids) by solving the following optimization problems, namely the optimal function: , This optimal function represents: For each points ( , represents the number of the points in set ), let be the smallest distance from to all points of S, is the farthest point from S if .

Flight data pattern discrimination algorithm based on k-means clustering
For the method of randomly selecting k centroids, we run k-means clustering algorithm 10 times on each group of data and get the clustering result with the smallest clustering error. The clustering error is computed by SSE (Sum of Squared Errors), and the distance between sampling points is calculated by Euclidean distance formula. The flight data pattern discrimination algorithm based on k-means clustering is described as PattDiscrBasedonKMeans, in which we suppose there are m kinds of flight modes.

Algorithm. PattDiscrBasedonKMeans( DataSet, GenerateCentMethod, ω):
# DataSet is the data set to be clustered, GenerateCentMethod is the two proposed methods to get the initial centroids, and ω is the centroid distance threshold of merging fault-free data.  In this way, we get the F values between each predefined class and each derived cluster. We generate the weighted mean value of F obtained by the different initial centroids selection methods used in this paper.
F-measure=sum(f[i][j]*the number of points in the predefined ith class) / the number of total points The larger the value is, the better the clustering result is.

Experimental design.
In this paper, we do experiments to 17 groups of fault flight data respectively. Two different methods are used to select the initial centroids, and the corresponding F values are calculated. At the same time, the accuracy of discrimination for the fault occurrence point is calculated.
In the course of the experiment, in accordance with the different flight mode, 29 groups of normal flight data are used to run the clustering algorithm with cluster number of 2. The distance between the two clusters of each flight mode is calculated, and the average value of the distances of the 29 sets of data is taken as the threshold for merging the clusters of the normal sampling points.

Results and analysis
For each group of flight data, we cluster it according to different modes, and then combine and manually correct the clustering results of different flight modes according to the time stamp of the sampling points.
In the clustering results obtained in a certain mode, the cluster composed of those points closer to starting time is classified as the normal class(fault free); the cluster composed of those points closer to ending time is classified as the after-crashing class (if the results are 3 clusters); the other points are classified as the fault class.
Thus, we get the final clustering result of a group of flight data. Then we calculate the values of indexes for the clustering results when running the clustering algorithms with different methods of generating initial centroids: Method1 and Method2, corresponding to the two methods in Section 3.2. The results are shown in Table 2 and Table 3.


text:
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