summaries: The authors present EDO-CS an approach to multi-objective optimisation that ensures the high quality and diversity of generated RL policies. Instead of uniformly sampling solutions from the Pareto front, sampling policies from learned clusters is introduced, as a selection mechanism within the ES optimisation. The quality and diversity are further achieved by modifying the objective function of the ES algorithm so it includes both the fitness and behaviour-diversity terms, balanced with a hyperparameter $\lambda$. This hyperparameter is set using a multi-arm bandit approach, which is adapted during the training.  The performance of the proposed approach is evaluated on several MuJoCo continuous control tasks, as well as compared to state-of-the-art QD benchmarks.

summaries: The authors present a new method for finding robust policies in reinforcement learning, those policies which give high rewards but also come from a diversity of behaviours. The authors accomplish this by using a clustering algorithm to first divide policies into relevant clusters and then use evolutionary algorithms to optimise policy choice. The result is an algorithm that performs well over several representative benchmarks, achieving SOTA performance with high convergence rates.

summaries: In the paper "Evolutionary Diversity Optimization With Clustering-Based Selection For Reinforcement Learning", the authors introduce a new selection mechanism for Quality-Diversity based algorithms. This new selection mechanism is based on the K-Means algorithm, to cluster the behaviour space into cells and then select only the best policies within each cell. The paper also uses a linear combination of the reward and novelty score when performing the policy updates. The weights the of the linear combination are automatically adjusted using a bandit algorithm so that the best reward is obtained.

summaries: This paper performs research in the area of diversity/novelty-seeking agents under evolutionary optimization approaches. The core idea in this area is to optimize a weighted combination between raw environment reward and diversity during training (even though evaluation is still on the raw environment reward only). The diversity acts as a "regularizer" in order to achieve better exploration, which can lead to higher rewards.  The specific approach (EDO-CS) by the paper suggests using a pool/"archive" $A$ of previous policies, which are then clustered via K-means according to the distance metric defined by the behavior function $b(\cdot)$. Each cluster then produces a new policy (and thus there are a total of $K$ new policies), which are then updated via ES over a regularized reward (via diversity metric, along with an adaptive weighting $\lambda$), and put back into the archive.   Experiments are performed over various continuous control benchmarks for testing exploration, and results show that EDO-CS achieves SOTA.

abstractText: Reinforcement Learning (RL) has achieved significant successes, which aims to obtain a single policy maximizing the expected cumulative rewards for a given task. However, in many real-world scenarios, e.g., navigating in complex environments and controlling robots, one may need to find a set of policies having both high rewards and diverse behaviors, which can bring better exploration and robust few-shot adaptation. Recently, some methods have been developed by using evolutionary techniques, including iterative reproduction and selection of policies. However, due to the inefficient selection mechanisms, these methods cannot fully guarantee both high quality and diversity. In this paper, we propose EDO-CS, a new Evolutionary Diversity Optimization algorithm with Clusteringbased Selection. In each iteration, the policies are divided into several clusters based on their behaviors, and a high-quality policy is selected from each cluster for reproduction. EDO-CS also adaptively balances the importance between quality and diversity in the reproduction process. Experiments on various (i.e., deceptive and multi-modal) continuous control tasks, show the superior performance of EDO-CS over previous methods, i.e., EDO-CS can achieve a set of policies with both high quality and diversity efficiently while previous methods cannot.

title: Using confidence bounds for exploitation-exploration trade-offs

venue: Journal of Machine Learning Research,

title: Evolutionary algorithms in theory and practice: Evolution Strategies, evolutionary programming, genetic algorithms

authors:
G. Cideron
T. Pierrot
N. Perrin
K. Beguir
O. Sigaud

authors:
C. Colas
V. Madhavan
J. Huizinga
J. Clune

authors:
A. Cully
Y. Demiris

authors:
A. Cully
J.-B. Mouret

authors:
A. Cully
J. Clune
D. Tarapore
J.-B. Mouret

title: Robots that can adapt like animals

authors:
K. Deb
A. Pratap
S. Agarwal
T. Meyarivan

authors:
A. Gaier
A. Asteroth
J.-B. Mouret

authors:
J. Lehman
K.O. Stanley

venue: Evolutionary Computation,

title: Least squares quantization in PCM

authors:
P. Mirowski
R. Pascanu
F. Viola
H. Soyer
A. Ballard
A. Banino
M. Denil
R. Goroshin
L. Sifre
K. Kavukcuoglu
D. Kumaran
R. Hadsell

authors:
J.-B. Mouret
J. Clune

authors:
O. Nilsson
A. Cully

title: Policy gradient assisted map-elites

authors:
J.K. Pugh
L.B. Soros
K.O. Stanley

venue: Frontiers in Robotics and AI,

authors:
N. Rakicevic
A. Cully
P. Kormushev

authors:
T. Salimans
J. Ho
X. Chen
S. Sidor
I. Sutskever

authors:
R.S. Sutton
A.G. Barto

title: Reinforcement learning: An introduction

authors:
V. Vassiliades
J.-B. Mouret

authors:
V. Vassiliades
K.I. Chatzilygeroudis
J.-B. Mouret

authors:
J. Vermorel
M. Mohri

authors:
Y. Zhu
R. Mottaghi
E. Kolve
J.J. Lim
A. Gupta
F.-F. Li
A. Farhadi

heading: 1 INTRODUCTION

text:
Reinforcement Learning (RL) is an effective method for training agents to make decisions in a given environment, which is often to obtain a policy maximizing the expected cumulative rewards (Li, 2017; Sutton & Barto, 2018). As RL is applied to more real-world scenarios, training a single policy is insufficient to handle complex problems, and we may need to find a set of policies with both high quality (i.e., rewards) and diverse behaviors. For example, when navigating in complex environments (Zhu et al., 2017; Mirowski et al., 2017), there are usually deceptive rewards trapping a single policy into the local optima. Maintaining a set of policies allows data to be collected with diverse behaviors and may lead to better exploration in these environments. When controlling robots, it is fragile to have one single policy (Cully et al., 2015). In contrast, maintaining a set of policies can improve robustness, e.g., enable real robots to recover quickly from joint damage (Cully et al., 2015), and also be helpful for few-shot adaption when facing unseen tasks (Kumar et al., 2020). General deep RL algorithms mostly focus on achieving high rewards, restricting their ability to generate diverse behaviors.
Evolutionary Algorithms (EAs) are general-purpose heuristic optimization algorithms that maintain a population (i.e., a set of solutions), and simulate the natural evolution process with iterative reproduction and selection (Bäck, 1996). Quality-Diversity (QD) algorithms (Pugh et al., 2016; Cully & Demiris, 2018) are a specific type of EAs that aim to return a set of high-quality solutions with diverse behaviors in a single run.
They have been naturally applied to RL in complex environments, generating the corresponding RL algorithms NSR-ES (Conti et al., 2018), ME-ES (Colas et al., 2020), DvD-ES (Parker-Holder et al., 2020) and QD-RL (Cideron et al., 2020). Note that classical QD algorithms like NSLC (Lehman & Stanley, 2011a) or MAP-Elites (Mouret & Clune, 2015; Cully et al., 2015) often employ a Genetic Algorithm (GA) as the underlying optimizer. However, as RL tasks are often high-dimensional, these methods have replaced GA with Evolution Strategies (ES) presented by Salimans et al. (2017), which has achieved performances comparable to state-of-the-art deep RL algorithms on high-dimensional control tasks.
NSR-ES (Conti et al., 2018) maintains a population of ES agents and introduces Novelty Search (NS) (Lehman & Stanley, 2011b) to improve the performance on RL tasks with sparse or deceptive rewards. That is, it adds a novelty term (representing behavior diversity) to the objective function of ES agents. In each iteration, NSR-ES selects a policy from the population for reproduction, where the probability of selecting a particular policy is proportional to its novelty score.
In contrast to NSR-ES (Conti et al., 2018), DvD-ES (Parker-Holder et al., 2020) optimizes all policies of a population simultaneously, by maximizing the sum of their rewards and a population-wide diversity criterion (i.e., the volume between the behaviors of the policies). Though DvD-ES can maintain a diverse population, it ignores the previously generated policies, leading to “cycling” (i.e., a phenomenon where the population keeps moving alternatively between two areas) and thus inefficient performance.
It has been shown (Cully & Demiris, 2018) that keeping an additional archive (i.e., a subset of policies generated-so-far) and selecting policies from the archive instead of the population for reproduction can be beneficial. There are different ways to select policies from the archive. ME-ES (Colas et al., 2020) uses an alternating selection mechanism, which selects several policies with the best quality in one iteration and with the best diversity in the next iteration. QD-RL (Cideron et al., 2020) uses Pareto-based selection (Deb et al., 2002) by considering both quality and diversity in one iteration, and achieves better performance. That is, the Pareto front is first calculated with respect to quality and diversity, and then the policies are selected from the Pareto front based on the crowding distance.
Although Pareto-based selection can guarantee the selected policies uniformly distributed over the Pareto front, these policies may be still similar in the behavior space, limiting the performance of QD-RL. For example, Figure 1(a) shows the heat map of a synthetic function f(x, y) in the behavior space, where the color corresponds to the function value, which we call quality here. The goal is to find the four optimal solutions distributed in the center of four regions of the behavior space. The points represent the solutions in the current archive, from which we need to select some solutions for reproduction. QD-RL first calculates the diversity of each solution (i.e., the average Euclidean distance between this solution and its k-nearest neighbors) in the archive, and then gets the Pareto front with respect to quality and diversity, as shown in Figure 1(b). By Pareto-based selection, the blue points together with the red star will be selected, which are uniformly distributed over the Pareto front, but concentrated in the lower right corner of the behavior space.
In this paper, we propose an Evolutionary Diversity Optimization algorithm with Clustering-based Selection (EDO-CS). In each iteration, the policies in the archive are divided into several clusters based on their behaviors, and a high-quality policy is selected from each cluster for reproduction. This selection mechanism can naturally guarantee the diversity of the selected policies in the behavior space. For example, the red points and red star in Figure 1(a) will be selected by clustering-based selection, which are distributed in the four different areas of the behavioral space.
To examine the performance of EDO-CS, we conduct experiments on a variety of continuous control tasks from OpenAI Gym library (Brockman et al., 2016). Firstly, we show that EDO-CS can solve navigating problems in environments with deceptive rewards. Then, we test it in multi-modal tasks, showing that EDOCS can efficiently find optimal policies with diverse behaviors. In the standard MuJoCo environments that do not require much diversity, we show that EDO-CS can achieve even better performance than Vanilla ES that focuses on the quality. We also test the influence of the hyper-parameters of EDO-CS in these environments.
The remainder of this paper is organized as follows. We first introduce some definitions and notations used in our paper in Section 2. After that, we propose our method in Section 3. The results and analyses of experiments are shown in Section 4. Finally, we conclude this work in Section 5.

heading: 2 BACKGROUND

text:
We consider the setting of a fully observable Markov Decision Process (MDP) described as a tuple (S,A, P,R, γ), where S is the state space, A is the action space, P (st+1|st, at) gives the probability of transiting to state st+1 after taking action at at state st, rt = R(st, at, st+1) is the reward obtained by transiting to state st+1 after taking action at at state st, and γ is the discount factor.
A policy πθ : S → A is a mapping from state space S to action space A, paremeterized by θ, which can be either deterministic or randomized. The goal of general RL algorithms is to optimize the parameters θ such that πθ maximizes the expectation of the cumulative rewards R(τ) = ∑T t=0 γ
trt, where τ is the trajectory over a horizon T . The objective function can be written as follows:
J(θ) = Eτ∼πθ [R(τ)] . (1)
To make better exploration and have more robustness, QD algorithms seek to find a set of policies with both high rewards and diverse behaviors (Pugh et al., 2016; Cully & Demiris, 2018). The behavior characterization b(πθ) of a policy πθ is usually domain-dependent. For example, it can be the coordinates of the final location (x, y) of the robot in the robot locomotion problem, and the corresponding behavior space is R2. It can also be defined as the actions taken by policies, leading to a high-dimensional behavior space. Given an archive A of policies, the diversity of a particular policy πθ is computed as the average Euclidean distance between b(πθ) and A′πθ,k, i.e., the set of k-nearest neighbors of πθ in the archive A:
Div(θ) = 1
k ∑ π′θ∈A ′ πθ ,k ‖b(πθ)− b(π′θ)‖2. (2)
Then, the objective function to be maximized can be expressed as:
J(θ) = (1− λ) · Eτ∼πθ [R(τ)] + λ ·Div(θ), (3) where λ controls the trade-off between the quality (i.e., rewards) and diversity.

heading: 3 THE EDO-CS ALGORITHM

text: In this section, we introduce the proposed algorithm, Evolutionary Diversity Optimization with Clusteringbased Selection (EDO-CS). We first give an overview of EDO-CS in Section 3.1. Then, we introduce the selection and reproduction mechanisms in Sections 3.2 and 3.3, respectively. Section 3.4 shows how to balance the quality and diversity. Finally, we compare EDO-CS with other QD algorithms in Section 3.5.

heading: 3.1 OVERVIEW

text: A general flow of EDO-CS is shown in Algorithm 1. It first initializes an archiveAwith a maximum capacity of l, which contains the policies generated-so-far together with their corresponding cumulative rewards and behaviors; and a bandit B, which is used to sample the weight of diversity (i.e., λ in Eq. (3)) during the reproduction process. Then, it adds l randomly generated policies into the archive A (lines 1–5), and tries to improve the policies in A iteratively (lines 7–20). In each iteration, EDO-CS employs K-means (Lloyd, 1982) to partition the policies in the archive into K clusters based on their behaviors (line 8), and selects one specific policy from each cluster (line 9). After getting K policies, EDO-CS samples the value of λ in the objective function for each policy from the bandit B, and uses the ES optimizer to update the selected policies in parallel for T ′ iterations (lines 11–15). The archive and bandit are updated in line 18 after evaluating all the generated offspring policies. To maintain the diversity of the archive, we avoid adding policies with similar behaviors (Cully & Mouret, 2013). To be specific, whenever we want to add a new policy into the archive, we first select the policy with the most similar behavior from the archive. If their behavior distance is greater than a threshold, we add the new policy into the archive. Otherwise, we compare their rewards and keep the policy with the higher reward. Note that if the archive size exceeds the capacity l after adding a new policy, the oldest policy in the archive will be deleted. EDO-CS repeats the above process until the number of iterations reaches T .

heading: 3.2 CLUSTERING-BASED SELECTION

text:
The selection process in each iteration of EDO-CS tries to select a set of high-quality policies with diverse behaviors from the archive. Here, we employ a natural and efficient way, i.e., clustering-based selection, which first clusters the policies in the archive and then selects a high-quality policy from each cluster. Clustering is an unsupervised algorithm for finding natural groups of a data set, such that the data in the same group (i.e., a cluster) are similar while those in different groups are not similar. For a given data set D = {x1,x2, · · · ,xn}, a clustering algorithm divides D into K clusters C = {C1, C2, · · · , CK} where ∀i 6= j, Ci ∩ Cj = ∅ and D = ∪Ki=1Ci. K-means (Lloyd, 1982) is one of the most popular clustering algorithms, which aims to minimize within-cluster variances, i.e.,
arg min C K∑ i=1 ∑ x∈Ci ‖x− µi‖2, (4)
where µi is the mean of points in Ci.
In the selection process, we first use K-means to cluster the policies in the archive based on their behaviors, which means x = b(πθ) in Eq. (4). Then, we select one specific policy πθi from each cluster Ci. More specifically, we first select the policy with the highest quality from the archive, and the corresponding cluster
Algorithm 1: EDO-CS Input: number of selected policies K, total number of iterations T , number of updating iterations T ′, behavior characterization b(πθ), archive size l, archive A, bandit B. Output: archive A // Warm up
1 for j = 1 : l do 2 Randomly generate policy πθj ; 3 Get cumulative rewards R and behavior b(πθj ) by evaluating the policy πθj ; 4 Add (πθj , R, b(πθj )) into archive A 5 end 6 t = 0; 7 while t < T do
// Selection 8 Use K-means to divide the policies in archive A into K clusters {Ck}Kk=1; 9 Select K policies {πθk}Kk=1, each one from a cluster;
// Reproduction 10 for k = 1 : K do
// Update in parallel 11 Sample λk from the bandit B; 12 for i = 1 : T ′ do 13 Set the objective function J(θk) = (1− λk)Eτ∼πθk [R(τ)] + λkDiv(θk); 14 Use ES to update θk as Eq. (7) 15 end 16 Get cumulative rewards R and behavior b(πθ′k) by evaluating the updated policy πθ′k 17 end 18 Update archive A and bandit B; 19 t = t+ T ′
20 end
is denoted as Ci∗ . Then, for each other cluster Ci 6= Ci∗ , we find its M highest-quality policies and select one uniformly at random. Policies in the same cluster have similar behaviors, and each selected policy can be viewed as a representative of its cluster, which has the potential to reproduce a high-quality policy with this type of behavior. Thus, by this clustering-based selection process, we can select good policies from different areas of the behavior space for reproduction.
Note that some previous works (Vassiliades et al., 2017; 2018) have also introduced clustering into QD algorithms to ensure diversity. But the usages are quite different. Previous works use the grid-based container and employ clustering to partition a high-dimensional behavior space into well-spread geometric regions before running the iterative evolutionary process, while our EDO-CS employs clustering to select a set of high-quality solutions with diverse behaviors from the archive in each iteration.

heading: 3.3 ES-BASED REPRODUCTION

text:
To reproduce offspring solutions from the selected solutions, we use ES as the optimizer. Inspired by natural evolution, ES represents a broad class of population-based black-box optimization algorithms, while here we use the version introduced in Salimans et al. (2017), which has achieved performances comparable to stateof-the-art deep RL algorithms on high-dimensional control tasks. ES represents a population of parameters
θ by a distribution pφ, and seeks to optimize the expected objective value Eθ∼pφ [J(θ)] using stochastic gradient ascent, where J(θ) is an objective function to measure the goodness of parameters θ. Using the log-likelihood trick and estimating the expectation over n samples,
∇φEθ∼pφ [J(θ)] ≈ 1
n ∑n i=1 J(θ(i))∇φ log pφ(θ(i)). (5)
The n samples are drawn by adding additive Gaussian noise to the current parameter, i.e., θ(i) = θ + σ (i), where σ > 0 and (i) ∼ N (0, I). Thus, the gradient estimation in Eq. (5) becomes
∇φEθ∼pφ [J(θ)] ≈ 1
nσ ∑n i=1 J(θ + σ (i)) (i). (6)
Based on the above gradient estimation, the parameter θ will be updated as
θt+1 = θt + η
nσ ∑n i=1 J(θt + σ (i)) (i), (7)
where η is the learning rate of the ES optimizer. In this paper, we set J(θ) as Eq. (3), i.e., a weighted sum of quality and diversity. But as different values of the hyper-parameter λ in Eq. (3) may be required for different tasks as well as different stages of the same task, we self-adjust it based on multi-armed bandit, which will be presented in the next subsection.

heading: 3.4 ADAPTIVE BALANCE BETWEEN QUALITY AND DIVERSITY

text:
In Eq. (3), the reward and diversity correspond to exploitation and exploration, respectively, implying that the hyper-parameter λ controls the trade-off between exploitation and exploration. Here, we model the problem of setting an appropriate λ as a multi-armed bandit problem (Vermorel & Mohri, 2005) by treating each alternative λ as an arm of the bandit. Let Λ = {λ(1), λ(2), · · · , λ(m)} denote the set of alternative arms. For each arm λ(i), the gain of rewards after updating a policy with λ(i) is used as its reward. Note that to use the multi-arm bandit model, we have made a stationary assumption, i.e., disregarding the change of the reward distribution of each arm in the process of optimization.
The Upper Confidence Bounds (UCB) algorithm (Auer, 2002) is used to select a specific arm in each iteration. That is, the arm λt in iteration t is chosen as
λt = arg max λ(i)
µt(λ (i)) + c
√ ln t
Nt(λ(i)) , (8)
where c > 0, µt(λ(i)) is the estimated mean rewards of arm λ(i), and Nt(λ(i)) is the number of times we have selected λ(i). Note that µt(λ(i)) reflects the current knowledge of the algorithm in a condensed form and guides further exploitation, while √ ln t
Nt(λ(i)) (i.e., the widths of the confidence bounds) reflects
the uncertainty of the algorithm’s knowledge and guides further exploration. The ablation study of the effectiveness of multi-arm bandit can be found in Appendix A.2.

heading: 3.5 COMPARISON BETWEEN QD ALGORITHMS

text: Finally, we compare EDO-CS with other related QD algorithms from the perspective of EAs, as shown in Table 1. The second column gives the selection strategies, and the third column shows whether the quality or diversity is considered in the objective function for reproducing offspring solutions. In the column of “EAs type”, we use (µ+ λ) to denote that the algorithm maintains µ solutions in the population, and generates λ offspring solutions in each iteration. The last column indicates whether the algorithm selects the solutions from the archive.

heading: 4 EXPERIMENT

text: To examine the performance of EDO-CS, we conduct experiments on a variety of continuous control tasks from the OpenAI Gym library (Brockman et al., 2016), including deceptive, multi-modal and standard MuJoCo environments. We compare EDO-CS against Vanilla ES (Salimans et al., 2017), NSR-ES (Conti et al., 2018), CVT-MAP-Elites (Vassiliades et al., 2018), ME-ES (Colas et al., 2020), DvD-ES (Parker-Holder et al., 2020) and QD-RL (Cideron et al., 2020). For a fair comparison, we use the ES optimizer with the same hyper-parameters in all algorithms, and CVT-MAP-Elites is denoted as CVT-ES accordingly. The population sizeK of these algorithms is always set to 5. For EDO-CS, the numberM of candidates for selection in each cluster is set to 2, and the arms of the bandit are {λ(1) = 0, λ(2) = 0.5}. Other parameter settings can be found in Appendix A.1. To have a sample-wise fair comparison, each algorithm uses the same number (i.e., 3000) of generations of ES optimizer. Note that each of the 600 iterations in the x-axis of all figures corresponds to five generations. Thus, for Vanilla ES and NSR-ES which reproduce only one policy in each iteration, one unit in the x-axis actually corresponds to their five iterations. Other algorithms reproduce five policies in each iteration, and thus one unit in the x-axis just corresponds to their one iteration. We report the mean and standard deviations across six identical seeds (2016 - 2021) for all algorithms and all tasks.

heading: 4.1 DECEPTIVE ENVIRONMENTS

text:
First, we consider an environment with deceptive rewards, which is modified from the standard Ant-v2 environment. As shown in Figure 2(a), a U-shape wall is in front of the ant, separating the ant from the target, i.e., green cuboid. The reward is a mixture of distance away from the target and costs for joint torques, encouraging the ant to walk to the target as fast as possible. Obviously, following the gradient of only the expected cumulative rewards will make the ant walk forward directly and get trapped by the wall. Here we use the final location (x, y) of the ant as the behavior characterization.
Figure 2(b) shows the rewards of the best-performing policy in the current archive in each iteration. As expected, both Vanilla ES and DvD-ES fail to get past the wall, because they do not use an archive to record previously explored policies, and thus cannot ensure diversity, leading to bad exploration under deceptive environments. NSR-ES can converge fast, but will finally get trapped into a local optimum. This is because NSR-ES reproduces only one policy in each iteration, and may update the same policy for several iterations, which can cause a rapid improvement of a particular policy but may also lead to a sub-optimal policy due to the lack of considering the whole behavior space. Among the previous algorithms we have compared, only QD-RL can finally obtain the optimal policy, but its convergence speed is slow. We can observe that our proposed algorithm EDO-CS can converge to the optimal policy much faster, showing the advantage of clustering-based selection.

heading: 4.2 MULTI-MODAL ENVIRONMENTS

text:
Next, we create two multi-modal environments to explicitly examine whether EDO-CS can efficiently find high-quality policies with diverse behaviors. The created HalfCheetahFwdBwd and AntFwdBwd environments are based on HalfCheetah-v2 and Ant-v2, respectively. In the HalfCheetahFwdBwd environment, instead of rewarding the agent for walking forward only, we assign rewards for both walking forward and backward, implying that there are two modals in this environment, i.e., walking forward and walking backward. We train policies in this multi-modal environment but test them in the single-modal environments HalfCheetahFwd and HalfCheetahBwd. The best-performing policies for these two modals are reported, respectively. We use the final location (x, y) of the agent as the behavior characterization. The AntFwdBwd environment is created similarly.
To compare different algorithms more clearly, we organize the experimental results into a tabular form. Table 2 reports the cumulative rewards, together with the average performance rankings of all algorithms in the four environments. We can observe that Vanilla ES can only learn a single modal, i.e., walking backward in HalfCheetahFwdBwd and walking forward in AntFwdBwd. This is because Vanilla ES maintains one policy, which can take only one action given a fixed state. As expected, all the other algorithms maintain a population of policies, and thus can achieve better performance than Vanilla ES in the multi-modal environments. DvD-ES can learn both modals in AntFwdBwd, but a single modal in HalfCheetahFwdBwd. NSR-ES, ME-ES, CVT-ES and QD-RL can learn both modals in both environments, but the quality of each modal is less satisfactory due to their inefficient selection mechanisms. We can observe that EDO-CS can learn any modal, and always achieves the highest quality in each modal, validating that EDO-CS can find a set of high-quality policies with diverse behaviors.

heading: 4.3 SINGLE-MODAL ENVIRONMENTS

text:
To examine the performance of EDO-CS for solving tasks that do not require much diversity, we conduct experiments in standard MuJoCo environments. Here we adopt the action-based behavior characterization, which was also used in (Parker-Holder et al., 2020). The behavior characterization b(πθ) of a particular deterministic policy πθ is represented in a vectorized form: b(πθ) = {πθ(·|s)}s∈S , where S is the state space, and πθ(· | s) corresponds to the action taken in state s under policy πθ. Since the state space can be infinitely large, we randomly sample 20 states instead of all. We compare all algorithms used before, except ME-ES, which requires discretization of the behavior space and is hard to be applied to high dimensional behavior space. Figure 3 shows the results of different algorithms on four standard MuJoCo tasks. We can observe that EDO-CS can always achieve the best final performance. Although Vanilla ES and NSR-ES can sometimes converge faster at the early stage of optimization, e.g., in the Humanoid-v2 environment, their final performance is limited. The performance of DVD-ES and QD-RL is dominated by that of EDO-CS, because their curves are always below that of EDO-CS.
By visualizing the clusters in different iterations of EDO-CS, we find that a set of diverse policies can be indeed selected from the archive through clustering-based selection. By the comparison with fixed λ, we also validate the effectiveness of self-adjusting λ in Eq. (3) using multi-arm bandit modeling. The influence of the hyper-parameters (including clustering algorithm, number of updating iterations T ′, population size K and archive size l) on the performance of EDO-CS are investigated as well. Due to space limitation, these experimental results are provided in Appendix A.2.

heading: 5 CONCLUSION

text:
QD algorithms aim to help RL to find a set of high-quality policies with diverse behaviors in complex environments. However, existing algorithms cannot fully guarantee both quality and diversity, mainly because of their inefficient selection mechanisms. In this paper, we propose the algorithm EDO-CS using clusteringbased selection, and demonstrate its superiority by experiments on various control tasks.
We have used ES as the optimizer. In fact, EDO-CS can also be equipped with the sample-efficient policy optimizer (Nilsson & Cully, 2021), which may further improve the performance. The mechanism of selfadjusting λ by multi-arm bandit modeling can be replaced by state-of-the-art online-learning algorithms, which may better balance the importance of quality and diversity. In addition, how to decide the population size automatically is also a matter of interest. One possible approach is to let the clustering algorithm determine the number of clusters by itself. Another interesting future work is to combine EDO-CS with representations or manifolds learning (Vassiliades & Mouret, 2018; Gaier et al., 2020; Rakicevic et al., 2021) in the parameter space or behavior space.

heading: T. Bäck. Evolutionary algorithms in theory and practice: Evolution Strategies, evolutionary programming,

text:
genetic algorithms. Oxford University Press, 1996.
G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba. OpenAI Gym. CoRR abs/1606.01540, 2016.
G. Cideron, T. Pierrot, N. Perrin, K. Beguir, and O. Sigaud. QD-RL: Efficient mixing of quality and diversity in reinforcement learning. CoRR abs/2006.08505, 2020.
C. Colas, V. Madhavan, J. Huizinga, and J. Clune. Scaling map-elites to deep neuroevolution. In Proceedings of the 22nd Genetic and Evolutionary Computation Conference (GECCO), pp. 67–75, Cancún, Mexico, 2020.
E. Conti, V. Madhavan, F. P. Such, J. Lehman, K. O. Stanley, and J. Clune. Improving exploration in evolution strategies for deep reinforcement learning via a population of novelty-seeking agents. In Advances in Neural Information Processing Systems 32 (NeurIPS), pp. 5032–5043, Montréal, Canada, 2018.
A. Cully and Y. Demiris. Quality and diversity optimization: A unifying modular framework. IEEE Transactions on Evolutionary Computation, 22(2):245–259, 2018.
A. Cully and J.-B. Mouret. Behavioral repertoire learning in robotics. In Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation (GECCO), pp. 175–182, New York, NY, 2013.
A. Cully, J. Clune, D. Tarapore, and J.-B. Mouret. Robots that can adapt like animals. Nature, 521(7553): 503–507, 2015.
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182–197, 2002.
A. Gaier, A. Asteroth, and J.-B. Mouret. Discovering representations for black-box optimization. In Proceeding of the 22nd Genetic and Evolutionary Computation Conference (GECCO), pp. 103–111, Cancún, Mexico, 2020.
S. Kumar, A. Kumar, S. Levine, and C. Finn. One solution is not all you need: Few-shot extrapolation via structured MaxEnt RL. In Advances in Neural Information Processing Systems 33 (NeurIPS), pp. 8198–8210, Vancouver, Canada, 2020.
J. Lehman and K. O. Stanley. Evolving a diversity of virtual creatures through novelty search and local competition. In Proceedings of the 13th Genetic and Evolutionary Computation Conference (GECCO), pp. 211–218, Dublin, Ireland, 2011a.
J. Lehman and K. O. Stanley. Abandoning objectives: Evolution through the search for novelty alone. Evolutionary Computation, 19(2):189–223, 2011b.
Y. Li. Deep reinforcement learning: An overview. CoRR abs/1701.07274, 2017.
S. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2):129–137, 1982.
P. Mirowski, R. Pascanu, F. Viola, H. Soyer, A. Ballard, A. Banino, M. Denil, R. Goroshin, L. Sifre, K. Kavukcuoglu, D. Kumaran, and R. Hadsell. Learning to navigate in complex environments. In Proceedings of the 5th International Conference on Learning Representations (ICLR), Toulon, France, 2017.
J.-B. Mouret and J. Clune. Illuminating search spaces by mapping elites. CoRR abs/1504.04909, 2015.
O. Nilsson and A. Cully. Policy gradient assisted map-elites. In Proceedings of the 23th Genetic and Evolutionary Computation Conference (GECCO), pp. 866–875, Lille, France, 2021.
J. Parker-Holder, A. Pacchiano, K. M. Choromanski, and S. J. Roberts. Effective diversity in population based reinforcement learning. In Advances in Neural Information Processing Systems 33 (NeurIPS), pp. 18050–18062, Vancouver, Canada, 2020.
J. K. Pugh, L. B. Soros, and K. O. Stanley. Quality diversity: A new frontier for evolutionary computation. Frontiers in Robotics and AI, 3:40, 2016.
N. Rakicevic, A. Cully, and P. Kormushev. Policy manifold search: Exploring the manifold hypothesis for diversity-based neuroevolution. In Proceeding of the 23th Genetic and Evolutionary Computation Conference (GECCO), pp. 901–909, Lille, France, 2021.
T. Salimans, J. Ho, X. Chen, S. Sidor, and I. Sutskever. Evolution strategies as a scalable alternative to reinforcement learning. CoRR abs/1703.03864, 2017.
R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT Press, 2018.
V. Vassiliades and J.-B. Mouret. Discovering the elite hypervolume by leveraging interspecies correlation. In Proceedings of the 20th Genetic and Evolutionary Computation Conference (GECCO), pp. 149–156, Kyoto, Japan, 2018.
V. Vassiliades, K. I. Chatzilygeroudis, and J.-B. Mouret. A comparison of illumination algorithms in unbounded spaces. In Proceeding of the 19th Genetic and Evolutionary Computation Conference Companion (GECCO), pp. 1578–1581, Berlin, Germany, 2017.
V. Vassiliades, K. I. Chatzilygeroudis, and J.-B. Mouret. Using centroidal voronoi tessellations to scale up the multidimensional archive of phenotypic elites algorithm. IEEE Transactions on Evolutionary Computation, 22(4):623–630, 2018.
J. Vermorel and M. Mohri. Multi-armed bandit algorithms and empirical evaluation. In Proceedings of the 16th European Conference on Machine Learning (ECML), pp. 437–448, Porto, Portugal, 2005.
Y. Zhu, R. Mottaghi, E. Kolve, J. J. Lim, A. Gupta, F.-F. Li, and A. Farhadi. Target-driven visual navigation in indoor scenes using deep reinforcement learning. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp. 3357–3364, Singapore, 2017.

heading: A APPENDIX

text:
A.1 HYPER-PARAMETERS
This section will introduce the hyper-parameters used in our experiments. For fair comparison, all the hyperparameters of different algorithms are set to be same in each environment.
A.2 ADDITIONAL EXPERIMENTAL RESULTS
Visualization of clusters We visualize the clusters in different iterations of EDO-CS for the experiments under the AntWall-v0 environment. Figure 4 shows the behavior space, where the points represent the solutions in the current archive, and the different colors represent the different clusters. Throughout the optimization process, we can observe that the solutions in the archive can always be partitioned into clusters with different behaviors, validating the effectiveness of clustering-based selection. As the optimization goes, the clusters can spread different regions of the behavior space better, also implying that EDO-CS can indeed find a set of diverse policies.
Adaptive λ. EDO-CS self-adjusts the hyper-parameter λ in Eq. 3 by multi-arm bandit modeling. A larger λ implies a larger weight of diversity when doing reproduction with ES. We have used {λ(1) = 0, λ(2) = 0.5} as the two arms in the experiments. To examine the effectiveness of this adaptive mechanism, we compare it with fixed λ ∈ {0, 0.5} in deceptive and multi-modal environments. The results in Table 5 show that the adaptive setting of λ always leads to the best performance.
Clustering algorithm. An essential step of EDO-CS is to cluster policies in the behavior space. We have adopted the K-means clustering algorithm because of its popularity. However, it is interesting to examine whether the choice of clustering algorithm will affect the performance of EDO-CS largely. Thus, we conduct experiments over various clustering algorithms, including Hierarchical Agglomerative Clustering (HAC), K-means, Balanced Iterative Reducing, Clustering Using Hierarchies (BIRCH) and Spectral Clustering. Figure 5 shows that these clustering algorithms except BIRCH can lead to the similar performance of EDO-CS in most cases. BIRCH is suitable for a large number of samples, while the number of policies in the archive is relatively small. Thus, we may not get good clustering results by BIRCH, degrading the performance of EDO-CS.
Number of updating iterations T ′. We also study the influence of the number of updating iterations T ′, i.e., the number of iterations for which we use ES to update the policy (in lines 12–15 of Algorithm 1) after selecting it from the archive. We have tested T ′ ∈ {5, 10, 15, 20} under various environments. The results in Table 6 show that the performance of EDO-CS is not very sensitive to T ′. Note that we have also tried to update the selected policy for only one iteration (i.e., set T ′ = 1), but it fails. If the number of updating iterations is too small, the difference between solutions will be insignificant, leading to ineffective selection.
Population size K. The population size K refers to the number of policies we select from the archive in each iteration. If the population size is too small, we may not be able to find all optimal policies with diverse behaviors; if the population size is too large, some policies with similar behavior will be selected and updated, harming the efficiency of the EDO-CS algorithm. Thus, it is important to select a proper population size K.
Table 7 shows the performance of EDO-CS under different population sizes. For a sample-wise fair comparison, we report the results under the same number of interactions with the environment rather than under the same number of iterations. It can be observed that the default population size of K = 5 is appropriate in most environments.
Figure 6 shows the performance of EDO-CS with different population sizes, given the same number of iterations. As expected, a larger population size implies a greater number of interactions with the environment, and thus results in a better performance of EDO-CS.
Archive size l. The archive is used to record the high-quality policies with diverse behaviors generatedso-far. It is crucial for EDO-CS, as the parent policies for reproduction in each iteration are selected from the archive. If the archive size l is too small, some useful information may be lost. If l is too large, it will contain lots of low-quality policies encountered before, the selection of which for reproduction will lower the efficiency. Figure 7 shows the results under different archive sizes. It would be interesting to investigate how to adaptively set the archive size of QD algorithms.


summaries: This paper studies the problem of distributed linear stochastic approximation for a group of agents over time-varying directed communication networks (to be more specific, the setup is decentralized). The authors propose two decentralized algorithms, (1) consensus-based linear stochastic approximation using row-stochastic mixing matrices (Eq. (1)), and (2) a push-sum type algorithm using column-stochastic mixing matrices (Eq. (9)). They further provide results on the asymptotic and finite-time mean-square errors to the equilibrium point of the (proper) ODE for each proposed algorithm.

summaries: An interesting submission dealing with distributed stochastic approximation driven by Markovian noise, in which the communication topologies considered among agents are captured by a stochastic matrix (in contrast to the doubly stochastic matrix studied in the related literature). Both asymptotic and finite-time error bounds are established and it was shown that the algorithm converges to some unspecified convex combination of the equilibrium points of local tasks. This paper finally proposes a push-type distributed stochastic approximation algorithm and provides its finite-time bounds for the performance by leveraging the analysis for the consensus-type algorithm with stochastic matrices. All analysis and error bounds are directly applicable to distributed TD algorithms.

summaries: This paper studies multi-agent distributed optimization under general consensus-type interactions between agents. The main contribution of the paper is to study linear stochastic approximation in a multi-agent setup without using bi-directional communication among agents. Non-asymptotic upper bounds on the associated error function, in a mean squared sense, are derived.

summaries: This paper addresses a consensus problem in stochastic approximation, which has application to policy iteration in reinforcement learning. Specifically, the authors address the case where the interaction graph between agents is stochastic, but not doubly stochastic. Under certain assumptions, the authors prove convergence of their proposed algorithm in a certain sense.

abstractText: This paper considers a novel multi-agent linear stochastic approximation algorithm driven by Markovian noise and general consensus-type interaction, in which each agent evolves according to its local stochastic approximation process which depends on the information from its neighbors. The interconnection structure among the agents is described by a time-varying directed graph. While the convergence of consensus-based stochastic approximation algorithms when the interconnection among the agents is described by doubly stochastic matrices (at least in expectation) has been studied, less is known about the case when the interconnection matrix is simply stochastic. For any uniformly strongly connected graph sequences whose associated interaction matrices are stochastic, the paper derives finite-time bounds on the mean-square error, defined as the deviation of the output of the algorithm from the unique equilibrium point of the associated ordinary differential equation. For the case of interconnection matrices being stochastic, the equilibrium point can be any unspecified convex combination of the local equilibria of all the agents in the absence of communication. Both the cases with constant and time-varying step-sizes are considered. In the case when the convex combination is required to be a straight average and interaction between any pair of neighboring agents may be uni-directional, so that doubly stochastic matrices cannot be implemented in a distributed manner, the paper proposes a push-type distributed stochastic approximation algorithm and provides its finite-time bounds for the performance by leveraging the analysis for the consensus-type algorithm with stochastic matrices.

authors:
P. Bianchi
G. Fort
W. Hachem

title: Performance of a distributed stochastic approximation algorithm

venue: IEEE Transactions on Information Theory,

title: Finite non-homogeneous chains

venue: Annals of Mathematics,

authors:
S. Boyd
A. Ghosh
B. Prabhakar
D. Shah

title: Randomized gossip algorithms

authors:
M. Cao
A.S. Morse
B.D.O. Anderson

title: Reaching a consensus in a dynamically changing environment: a graphical approach

venue: SIAM Journal on Control and Optimization,

authors:
J. Chen
A.H. Sayed

title: Diffusion adaptation strategies for distributed optimization and learning over networks

venue: IEEE Transactions on Signal Processing,

authors:
T.T. Doan
S.T. Maguluri
J. Romberg

title: Finite-time analysis of distributed TD(0) with linear function approximation on multi-agent reinforcement learning

venue: In 36th International Conference on Machine Learning,

title: Finite-time performance of distributed temporaldifference learning with linear function approximation

venue: SIAM Journal on Mathematics of Data Science,

authors:
B. Gharesifard
J. Cortés

title: Distributed strategies for generating weight-balanced and doubly stochastic digraphs

venue: European Journal of Control,

title: Stochastic approximation for consensus: a new approach via ergodic backward products

venue: IEEE Transactions on Automatic Control,

authors:
A. Jadbabaie
J. Lin
A.S. Morse

title: Coordination of groups of mobile autonomous agents using nearest neighbor rules

authors:
D. Kempe
A. Dobra
J. Gehrke

title: Gossip-based computation of aggregate information

venue: IEEE Symposium on Foundations of Computer Science,

title: Zur theorie der markoffschen ketten

venue: Mathematische Annalen,

authors:
H.J. Kushner
G. Yin

title: Asymptotic properties of distributed and communicating stochastic approximation algorithms

authors:
H.J. LeBlanc
H. Zhang
X. Koutsoukos
S. Sundaram

title: Resilient asymptotic consensus in robust networks

venue: IEEE Journal on Selected Areas in Communications,

authors:
A. Nedić
J. Liu

title: On convergence rate of weighted-averaging dynamics for consensus problems

authors:
A. Nedić
A. Olshevsky

title: Distributed optimization over time-varying directed graphs

authors:
A. Nedić
A. Olshevsky
A. Ozdaglar
J.N. Tsitsiklis

title: On distributed averaging algorithms and quantization effects

venue: IEEE Transactions on automatic control,

authors:
A. Nedić
A. Olshevsky
M.G. Rabbat

title: Network topology and communication-computation tradeoffs in decentralized optimization

venue: Proceedings of the IEEE,

authors:
R. Olfati-Saber
J.A. Fax
R.M. Murray

title: Consensus and cooperation in networked multi-agent systems

venue: Proc. IEEE,

authors:
A. Olshevsky
J.N. Tsitsiklis

title: On the nonexistence of quadratic lyapunov functions for consensus algorithms

title: Degree fluctuations and the convergence time of consensus algorithms

authors:
R. Srikant
L. Ying

title: Finite-time error bounds for linear stochastic approximation and TD learning

venue: In 32nd Conference on Learning Theory,

authors:
M.S. Stanković
N. Ilić
S.S. Stanković

title: Distributed stochastic approximation: weak convergence and network design

title: Stanković. Multi-agent temporal-difference learning with linear function approximation: Weak convergence under time-varying network topologies

venue: In American Control Conference,

authors:
S.S. Stanković
M.S. Stanković
D. Stipanović

title: Decentralized parameter estimation by consensus based stochastic approximation

authors:
J. Sun
G. Wang
G.B. Giannakis
Q. Yang
Z. Yang

title: Finite-time analysis of decentralized temporal-difference learning with linear function approximation

venue: In International Conference on Artificial Intelligence and Statistics,

authors:
W. Suttle
Z. Yang
K. Zhang
Z. Wang
T. Başar
J. Liu

title: A multi-agent off-policy actor-critic algorithm for distributed reinforcement learning

venue: In 21st IFAC World Congress,

title: Reinforcement Learning: An Introduction

venue: Cambridge: MIT press,

title: Product of Random Stochastic Matrices and Distributed Averaging

venue: Springer Science & Business Media,

title: Problems in Decentralized Decision Making and Computation

venue: PhD thesis, Department of Electrical Engineering and Computer Science,

authors:
J.N. Tsitsiklis
B. Van Roy

title: An analysis of temporal-difference learning with function approximation

authors:
N.H. Vaidya
L. Tseng
G. Liang

title: Iterative approximate byzantine consensus in arbitrary directed graphs

venue: In Proceedings of the 2012 ACM symposium on Principles of distributed computing,

authors:
G. Wang
S. Lu
G. Giannakis
G. Tesauro
J. Sun

title: Decentralized TD tracking with linear function approximation and its finite-time analysis

venue: In 34th Conference on Neural Information Processing Systems,

authors:
L. Xiao
S. Boyd
S. Lall

title: A scheme for robust distributed sensor fusion based on average consensus

venue: In Proceedings of the 4th International Conference on Information Processing in Sensor Networks,

authors:
S. Zeng
T.T. Doan
J. Romberg

title: Finite-time analysis of decentralized stochastic approximation with applications in multi-agent and multi-task learning

venue: arXiv preprint arXiv:2010.15088,

authors:
K. Zhang
Z. Yang
T. Başar

title: Networked multi-agent reinforcement learning in continuous spaces

venue: In 57th IEEE Conference on Decision and Control,

authors:
K. Zhang
Z. Yang
H. Liu
T. Zhang
T. Başar

title: Fully decentralized multi-agent reinforcement learning with networked agents

venue: In 35th International Conference on Machine Learning,

title: Multi-agent reinforcement learning: A selective overview of theories and algorithms

venue: arXiv preprint arXiv:1911.10635,

title: Finite-sample analysis for decentralized batch multi-agent reinforcement learning with networked agents

authors:
Y. Zhang
M.M. Zavlanos

title: Distributed off-policy actor-critic reinforcement learning with policy consensus

venue: In 58th IEEE Conference on Decision and Control,

heading: 1 INTRODUCTION

text:
The use of reinforcement learning (RL) to obtain policies that describe solutions to a Markov decision process (MDP) in which an autonomous agent interacting with an unknown environment aims to optimize its long term reward is now standard Sutton & Barto (1998). Multi-agent or distributed reinforcement learning is useful when a team of agents interacts with an unknown environment or system and aims to collaboratively accomplish tasks involving distributed decision-making. Distributed here implies that agents exchange information only with their neighbors according to a certain communication graph. Recently, many distributed algorithms for multi-agent RL have been proposed and analyzed (Zhang et al., 2019). The basic result in such works is of the type that if the graph describing the communication among the agents is bi-directional (and hence can be represented by a doubly stochastic matrix), then an algorithm that builds on traditional consensus algorithms converges to a solution in terms of policies to be followed by the agents that optimize the sum of the utility functions of all the agents; further, both finite and infinite time performance of such algorithms can be characterized (Doan et al., 2019; Zhang et al., 2018b).
This paper aims to relax the assumption of requiring bi-directional communication among agents in a distributed RL algorithm. This assumption is arguably restrictive and will be violated due to reasons such as packet drops or delays, differing privacy constraints among the agents, heterogeneous capabilities among the agents in which some agents may be able to communicate more often or with more power than others, adversarial attacks, or even sophisticated resilient consensus algorithms being used to construct the distributed RL algorithm. A uni-directional communication graph can be represented through a (possibly time-varying) stochastic – which may not be doubly stochastic – matrix being used in the algorithm. As we discuss in more detail below, relaxing the assumption of a doubly stochastic matrix to simply a stochastic matrix in the multi-agent and distributed RL algorithms that have been proposed in the literature, however, complicates the proofs of their convergence and finite time performance characterizations. The main result in this paper is to provide a finite time bound on the mean-square error for a multi-agent linear stochastic approximation algorithm in which the agents interact over a time-varying directed graph characterized by a stochastic matrix. This paper, thus, extends the applicability of distributed and multi-agent RL
algorithms presented in the literature to situations such as those mentioned above where bidirectional communication at every time step cannot be guaranteed. As we shall see, this extension is technically challenging and requires new proof techniques that may be of independent interest.
Related Work (See Appendix B for more related work) Many distributed reinforcement learning algorithms have now been proposed in the literature. In this setting, each agent can receive information only from its neighbors, and no single agent can solve the problem alone or by ‘taking the lead’. A backbone of almost all distributed RL algorithms proposed in the literature is the consensus-type interaction among the agents, dating back at least to Tsitsiklis (1984). Many works have analyzed asymptotic convergence of such RL algorithms using ODE methods (Zhang & Zavlanos, 2019; Zhang et al., 2018b; Suttle et al., 2020; Zhang et al., 2018a). This can be viewed as an application of ideas from distributed stochastic approximation (Kushner & Yin, 1987; Stanković et al., 2010; Huang, 2012; Stanković & Stanković, 2016; Bianchi et al., 2013; Stanković et al., 2016). Finite-time performance guarantees for distributed RL have also been provided in works, most notably in Doan et al. (2019; 2021); Wang et al. (2020); Zhang et al. (2021); Sun et al. (2020); Zeng et al. (2020).
The assumption that is the central concern of this paper and is made in all the existing finite-time analyses for distributed RL algorithms is that the consensus interaction is characterized by doubly stochastic matrices (Doan et al., 2019; 2021; Wang et al., 2020; Zhang et al., 2021; Sun et al., 2020; Zeng et al., 2020) at every time step, or at least in expectation, i.e., W1 = 1 and 1>E(W ) = 1> (Bianchi et al., 2013). Intuitively, doubly stochastic matrices imply symmetry in the communication graph, which almost always requires bidirectional communication graphs. More formally, the assumption of doubly stochastic matrices is restrictive since distributed construction of a doubly stochastic matrix needs to either invoke algorithms such as the Metropolis algorithm (Xiao et al., 2005) which requires bi-directional communication of each agent’s degree information; or to utilize an additional distributed algorithm (Gharesifard & Cortés, 2012) which significantly increases the complexity of the whole algorithm design. Doubly stochastic matrices in expectation can be guaranteed via so-called broadcast gossip algorithms which still requires bi-directional communication for convergence (Bianchi et al., 2013). In a realistic network, especially with mobile agents such as autonomous vehicles, drones, or robots, uni-directional communication is inevitable due to various reasons such as asymmetric communication and privacy constraints, non-zero communication failure probability between any two agents at any given time, and application of resilient consensus in the presence of adversary attacks (Vaidya et al., 2012; LeBlanc et al., 2013), all leading to an interaction among the agents characterized by a stochastic matrix, which may further be timevarying. The problem of design of distributed RL algorithms with time-varying stochastic matrices and characterizing either their asymptotic convergence or finite time analysis remains open.
As a step towards solving this problem, we propose a novel distributed stochastic approximation algorithm and provide its convergence analyses when a time-dependent stochastic matrix is being used due to uni-directional communication in a dynamic network. One of the first guarantees to be lost as the assumption of doubly stochastic matrices is removed is that the algorithm converges to a “policy” that maximizes the sum of reward functions of all the agents. Instead, the convergence is to a set of policies that optimize a convex combination of the network-wise accumulative reward, with the exact combination depending on the limit product of the infinite sequence of stochastic matrices. Nonetheless, by defining the error as the deviation of the output of the algorithm from the eventual equilibrium point, we derive finite-time bounds on the mean-square error. We consider both the cases with constant and time-varying step sizes. In the important special case where the goal is to optimize the average of the individual accumulative rewards of all the agents, we provide a distributed stochastic approximation algorithm, which builds on the push-sum idea (Kempe et al., 2003) that has been used to solve distributed averaging problem over strongly connected graphs, and characterize its finite-time performance. Thus, this paper provides the first distributed algorithm that can be applied (e.g., in Temporal difference (TD) learning, see Appendix D) to converge to the policy maximizing the team objective of the sum of the individual utility functions over time-varying, unidirectional, communication graphs, and characterizes the finite-time bounds on the mean-square error of the algorithm output from the equilibrium point under appropriate assumptions.
Technical Innovation and Contributions There are two main technical challenges in removing the assumption of doubly stochastic matrices being used in the analysis of distributed stochastic approximation algorithms. The first is in the direction of finite-time analysis. For distributed RL algorithms, finite-time performance analysis essentially boils down to two parts, namely bounding the consensus error and bounding the “single-agent” mean-square error. For the case when consensus
interaction matrices are all doubly stochastic, the consensus error bound can be derived by analyzing the square of the 2-norm of the deviation of the current state of each agent from the average of the states of the agents. With consensus in the presence of doubly stochastic matrices, the average of the states of the agents remains invariant. Thus, it is possible to treat the average value as the state of a fictitious agent to derive the mean-square consensus error bound with respect to the limiting point. More formally, this process relies on two properties of a doubly stochastic matrix W , namely that (1) 1>W = 1>, and (2) if xt+1 = Wxt, then ‖xt+1 − (1>xt+1)1‖2 ≤ σ2(W )‖xt − (1>xt)1‖2 where σ2(W ) denotes the second largest singular value of W (which is strictly less than one if W is irreducible). Even if the doubly stochastic matrix is time-varying (denoted by Wt), property (1) still holds and property (2) can be generalized as in Nedić et al. (2018). Thus, the square of the 2-norm ‖xt − (1>xt)1‖22 is a quadratic Lyapunov function for the average consensus processes. Doubly stochastic matrices in expectation can be treated in the same way by looking at the expectation. This is the core on which all the existing finite-time analyses of distributed RL algorithms are based.
However, if each consensus interaction matrix is stochastic, and not necessarily doubly stochastic, the above two properties may not hold. In fact, it is well known that quadratic Lyapunov functions for general consensus processes xt+1 = Stxt, with St being stochastic, do not exist (Olshevsky & Tsitsiklis, 2008). This breaks down all the existing analyses and provides the first technical challenge that we tackle in this paper. Specifically, we appeal to the idea of quadratic comparison functions for general consensus processes. This was first proposed in Touri (2012) and makes use of the concept of “absolute probability sequences”. We provide a general analysis methodology and results that subsume the existing finite-time analyses for single-timescale distributed linear stochastic approximation and TD learning as special cases (see Appendix D).
The second technical challenge arises from the fact that with stochastic matrices, the distributed RL algorithms may not converge to the policies that maximize the average of the utility functions of the agents. To regain this property, we propose a new algorithm that utilizes a push-sum protocol for consensus. However, finite-time analysis for such a push-based distributed algorithm is challenging. Almost all, if not all, the existing push-based distributed optimization works build on the analysis in Nedić & Olshevsky (2014); however, that analysis assumes that a convex combination of the entire history of the states of each agent (and not merely the current state of the agent) is being calculated. This assumption no longer holds in our case. To obtain a direct finite-time error bound without this assumption, we propose a new approach to analyze our push-based distributed algorithm by leveraging our consensus-based analyses to establish direct finite-time error bounds for stochastic approximation. Specifically, we tailor an “absolute probability sequence” for the pushbased stochastic approximation algorithm and exploit its properties. Such properties have never been found in the existing literature and may be of independent interest for analyzing any push-sum based distributed algorithm.
We now list the main contributions of our work. We propose a novel consensus-based distributed linear stochastic approximation algorithm driven by Markovian noise in which each agent evolves according to its local stochastic approximation process and the information from its neighbors. We assume only a (possibly time-varying) stochastic matrix being used during the consensus phase, which is a more practical assumption when only unidirectional communication is possible among agents. We establish both convergence guarantees and finite-time bounds on the mean-square error, defined as the deviation of the output of the algorithm from the unique equilibrium point of the associated ordinary differential equation. The equilibrium point can be an “uncontrollable” convex combination of the local equilibria of all the agents in the absence of communication. We consider both the cases of constant and time-varying step-sizes. Our results subsume the existing results on convergence and finite-time analysis of distributed RL algorithms that assume doubly stochastic matrices and bi-directional communication as special cases. In the case when the convex combination is required to be a straight average and interaction between any pair of neighboring agents may be uni-directional, we propose a push-type distributed stochastic approximation algorithm and establish its finite-time performance bound. It is worth emphasizing that it is straightforward to extend our algorithm from the straight average point to any pre-specified convex combination. Since it is well known that TD algorithms can be viewed as a special case of linear stochastic approximation (Tsitsiklis & Roy, 1997), our distributed linear stochastic approximation algorithms and their finitetime bounds can be applied to TD algorithms in a straight-forward manner; (see distributed TD(λ) in Appendix D).
Notation We use Xt to represent that a variable X is time-dependent and t ∈ {0, 1, 2, . . .} is the discrete time index. The ith entry of a vector x will be denoted by xi and, also, by (x)i when convenient. The ijth entry of a matrixAwill be denoted by aij and, also, by (A)ij when convenient. We use 1n to denote the vectors in Rn whose entries all equal to 1’s, and I to denote the identity matrix, whose dimension is to be understood from the context. Given a set S with finitely many elements, we use |S| to denote the cardinality of S. We use d·e to denote the ceiling function. A vector is called a stochastic vector if its entries are nonnegative and sum to one. A square nonnegative matrix is called a row stochastic matrix, or simply stochastic matrix, if its row sums all equal one. Similarly, a square nonnegative matrix is called a column stochastic matrix if its column sums all equal one. A square nonnegative matrix is called a doubly stochastic matrix if its row sums and column sums all equal one. The graph of an n × n matrix is a direct graph with n vertices and a directed edge from vertex i to vertex j whenever the ji-th entry of the matrix is nonzero. A directed graph is strongly connected if it has a directed path from any vertex to any other vertex. For a strongly connected graph G, the distance from vertex i to another vertex j is the length of the shortest directed path from i to j; the longest distance among all ordered pairs of distinct vertices i and j in G is called the diameter of G. The union of two directed graphs, Gp and Gq , with the same vertex set, written Gp ∪Gq , is meant the directed graph with the same vertex set and edge set being the union of the edge set of Gp and Gq . Since this union is a commutative and associative binary operation, the definition extends unambiguously to any finite sequence of directed graphs.

heading: 2 DISTRIBUTED LINEAR STOCHASTIC APPROXIMATION

text:
Consider a network consisting of N agents. For the purpose of presentation, we label the agents from 1 through N . The agents are not aware of such a global labeling, but can differentiate between their neighbors. The neighbor relations among the N agents are characterized by a time-dependent directed graph Gt = (V, Et) whose vertices correspond to agents and whose directed edges (or arcs) depict neighbor relations, where V = {1, . . . , N} is the vertex set and Et = V × V is the edge set at time t. Specifically, agent j is an in-neighbor of agent i at time t if (j, i) ∈ Et, and similarly, agent k is an out-neighbor of agent i at time t if (i, k) ∈ Et. Each agent can send information to its out-neighbors and receive information from its in-neighbors. Thus, the directions of edges represent the directions of information flow. For convenience, we assume that each agent is always an in- and out-neighbor of itself, which implies that Gt has self-arcs at all vertices for all time t. We use N it and N i−t to denote the in- and out-neighbor set of agent i at time t, respectively, i.e., N it = {j ∈ V : (j, i) ∈ Et}, N i−t = {k ∈ V : (i, k) ∈ Et}. It is clear that N it and N i−t are nonempty as they both contain index i. We propose the following distributed linear stochastic approximation over a time-varying neighbor graph sequence {Gt}. Each agent i has control over a random vector θit which is updated by
θit+1 = ∑ j∈N it wijt θ j t + αt ( A(Xt) ∑ j∈N it wijt θ j t + b i(Xt) ) , i ∈ V, t ∈ {0, 1, 2, . . .}, (1)
where wijt are consensus weights, αt is the step-size at time t, A(Xt) is a random matrix and b i(Xt) is a random vector, both generated based on the Markov chain {Xt} with state spaces X . It is worth noting that the update of each agent only uses its in-neighbors’ information and thus is distributed.
Remark 1 The work of Kushner & Yin (1987) considers a different consensus-based networked linear stochastic approximation as follows:
θit+1 = ∑ j∈N it wijt θ j t + αt ( A(Xt)θ i t + b i(Xt) ) , i ∈ V, t ∈ {0, 1, 2, . . .}, (2)
whose state form is Θt+1 = WtΘt+αtΘtA(Xt)>+αtB(Xt), and mainly focuses on asymptotically weakly convergence for the fixed step-size case (i.e., αt = α for all t). Under the similar set of conditions, with its condition (C3.4’) being a stochastic analogy for Assumption 6, Theorem 3.1 in Kushner & Yin (1987) shows that equation 2 has a limit which can be verified to be the same as θ∗, the limit of equation 1. How to apply the finite-time analysis tools in this paper to equation 2 has so far eluded us. The two updates equation 1 and equation 2 are analogous to the “combine-thenadapt” and “adapt-then-combine” diffusion strategies in distributed optimization (Chen & Sayed, 2012).
We impose the following assumption on the weights wijt which has been widely adopted in consensus literature (Jadbabaie et al., 2003; Olfati-Saber et al., 2007; Nedić & Liu, 2017).
Assumption 1 There exists a constant β > 0 such that for all i, j ∈ V and t, wijt ≥ β whenever j ∈ N it . For all i ∈ V and t, ∑ j∈N it wijt = 1.
Let Wt be the N × N matrix whose ijth entry equals wijt if j ∈ N it and zero otherwise. From Assumption 1, each Wt is a stochastic matrix that is compliant with the neighbor graph Gt. Since each agent i is always assumed to be an in-neighbor of itself, all diagonal entries of Wt are positive. Thus, if Gt is strongly connected, Wt is irreducible and aperiodic. To proceed, define
Θt =  (θ 1 t ) >
... (θNt ) >
 , B(Xt) =  (b 1(Xt)) >
... (bN (Xt)) >  . Then, the N linear stochastic recursions in equation 1 can be combined and written as
Θt+1 = WtΘt + αtWtΘtA(Xt) > + αtB(Xt), t ∈ {0, 1, 2, . . .}. (3)
The goal of this section is to characterize the finite-time performance of equation 1, or equivalently equation 3, with the following standard assumptions, which were adopted e.g. in Srikant & Ying (2019); Doan et al. (2019).
Assumption 2 There exists a matrix A and vectors bi, i ∈ V , such that
lim t→∞ E[A(Xt)] = A, lim t→∞
E[bi(Xt)] = b i, i ∈ V.
Define bmax = maxi∈V supx∈X ‖bi(x)‖2 < ∞ and Amax = supx∈X ‖A(x)‖2 < ∞. Then, ‖A‖2 ≤ Amax and ‖bi‖2 ≤ bmax, i ∈ V .
Assumption 3 Given a positive constant α, we use τ(α) to denote the mixing time of the Markov chain {Xt} for which ‖E[A(Xt)−A|X0 = X]‖2 ≤ α, ∀X, ∀t ≥ τ(α),‖E[bi(Xt)− bi|X0 = X]‖2 ≤ α, ∀X, ∀t ≥ τ(α), ∀i ∈ V. The Markov chain {Xt} mixes at a geometric rate, i.e., there exists a constant C such that τ(α) ≤ −C logα.
Assumption 4 All eigenvalues of A have strictly negative real parts, i.e., A is a Hurwitz matrix. Then, there exists a symmetric positive definite matrix P , such that A>P + PA = −I . Let γmax and γmin be the maximum and minimum eigenvalues of P , respectively.
Assumption 5 The step-size sequence {αt} is positive, non-increasing, and satisfies ∑∞ t=0 αt =∞
and ∑∞ t=0 α 2 t <∞.
To state our first main result, we need the following concepts.
Definition 1 A graph sequence {Gt} is uniformly strongly connected if there exists a positive integer L such that for any t ≥ 0, the union graph∪t+L−1k=t Gk is strongly connected. If such an integer exists, we sometimes say that {Gt} is uniformly strongly connected by sub-sequences of length L.
Remark 2 Two popular joint connectivity definitions in consensus literature are “B-connected” (Nedić et al., 2009) and “repeatedly jointly strongly connected” (Cao et al., 2008). A graph sequence {Gt} is B-connected if there exists a positive integer B such that the union graph ∪(k+1)B−1t=kB Gt is strongly connected for each integer k ≥ 0. Although the uniformly strongly connectedness looks more restrictive compared with B-connectedness at first glance, they are in fact equivalent. To see this, first it is easy to see that if {Gt} is uniformly strongly connected, {Gt} must
be B-connected; now supposing {Gt} is B-connected, for any fix t, the union graph ∪t+2B−1k=t Gk must be strongly connected, and thus {Gt} is uniformly strongly connected by sub-sequences of length 2B. Thus, the two definitions are equivalent. It is also not hard to show that the uniformly strongly connectedness is equivalent to “repeatedly jointly strongly connectedness” provided the graphs under consideration all have self-arcs at all vertices, as “repeatedly jointly strongly connectedness” is defined upon “graph composition”.
Definition 2 Let {Wt} be a sequence of stochastic matrices. A sequence of stochastic vectors {πt} is an absolute probability sequence for {Wt} if π>t = π>t+1Wt for all t ≥ 0.
This definition was first introduced by Kolmogorov (Kolmogoroff, 1936). It was shown by Blackwell (Blackwell, 1945) that every sequence of stochastic matrices has an absolute probability sequence. In general, a sequence of stochastic matrices may have more than one absolute probability sequence; when the sequence of stochastic matrices is “ergodic”, it has a unique absolute probability sequence (Nedić & Liu, 2017). It is easy to see that when Wt is a fixed irreducible stochastic matrix W , πt is simply the normalized left eigenvector of W for eigenvalue one. More can be said.
Lemma 1 Suppose that Assumption 1 holds. If {Gt} is uniformly strongly connected, then there exists a unique absolute probability sequence {πt} for the matrix sequence {Wt} and a constant πmin ∈ (0, 1) such that πit ≥ πmin for all i and t.
Let 〈θ〉t = ∑N i=1 π i tθ i t, which is a column vector and convex combination of all θ i t. It is easy to see that 〈θ〉t = (π>t Θt)> = Θ>t πt. From Definition 2 and equation 3, we have π>t+1Θt+1 = π>t+1WtΘt +αtπ > t+1WtΘtA(Xt) >+αtπ > t+1B(Xt) = π > t Θt +αtπ > t ΘtA(Xt) >+αtπ > t+1B(Xt), which implies that
〈θ〉t+1 = 〈θ〉t + αtA(Xt)〈θ〉t + αtB(Xt)>πt+1. (4)
Asymptotic performance of equation 1 with any uniformly strongly connected neighbor graph sequence is characterized by the following two theorems.
Theorem 1 Suppose that Assumptions 1, 2 and 5 hold. Let {θit}, i ∈ V , be generated by equation 1. If {Gt} is uniformly strongly connected, then limt→∞ ‖θit − 〈θ〉t‖2 = 0 for all i ∈ V .
Theorem 1 only shows that all the sequences {θit}, i ∈ V , generated by equation 1 will finally reach a consensus, but not necessarily convergent or bounded. To guarantee the convergence of the sequences, we further need the following assumption, whose validity is discussed in Remark 3.
Assumption 6 The absolute probability sequence {πt} for the stochastic matrix sequence {Wt} has a limit, i.e., there exists a stochastic vector π∞ such that limt→∞ πt = π∞.
Theorem 2 Suppose that Assumptions 1–6 hold. Let {θit}, i ∈ V , be generated by equation 1 and θ∗ be the unique equilibrium point of the ODE
θ̇ = Aθ + b, b = N∑ i=1 πi∞b i, (5)
whereA and bi are defined in Assumption 2 and π∞ is defined in Assumption 6. If {Gt} is uniformly strongly connected, then all θit will converge to θ ∗ both with probability 1 and in mean square.
Remark 3 Though Assumption 6 may look restrictive at first glance, simple simulations show that the sequences {θit}, i ∈ V , do not converge if the assumption does not hold. It is worth emphasizing that the existence of π∞ does not imply the existence of limt→∞Wt, though the converse is true. Indeed, the assumption subsumes various cases including (a) all Wt are doubly stochastic matrices, and (b) all Wt share the same left eigenvector for eigenvalue 1, which may arise from the scenario when the number of in-neighbors of each agent does not change over time (Olshevsky & Tsitsiklis, 2013). An important implication of Assumption 6 is when the consensus interaction among the agents, characterized by {Wt}, is replaced by resilient consensus algorithms such as Vaidya et al. (2012); LeBlanc et al. (2013) in order to attenuate the effect of unknown malicious
agents, the resulting dynamics of non-malicious agents, in general, will not converge, because the resulting interaction stochastic matrices among the non-malicious agents depend on the state values transmitted by the malicious agents, which can be arbitrary, and thus the resulting stochastic matrix sequence, in general, does not have a convergent absolute probability sequence; of course, in this case, the trajectories of all the non-malicious agents will still reach a consensus as long as the step-size is diminishing, as implied by Theorem 1. Further discussion on Assumption 6 can be found in Appendix C.
We now study the finite-time performance of the proposed distributed linear stochastic approximation equation 1 for both fixed and time-varying step-size cases. Its finite-time performance is characterized by the following theorem.
Let ηt = ‖πt − π∞‖2 for all t ≥ 0. From Assumption 6, ηt converges to zero as t→∞.
Theorem 3 Let the sequences {θit}, i ∈ V , be generated by equation 1. Suppose that Assumptions 1–4, 6 hold and {Gt} is uniformly strongly connected by sub-sequences of length L. Let qt and mt be the unique integer quotient and remainder of t divided by L, respectively. Let δt be the diameter of ∪t+L−1k=t Gk, δmax = maxt≥0 δt, and
= ( 1 +
2bmax Amax − πminβ 2L 2δmax
) (1 + αAmax)
2L − 2bmax Amax (1 + αAmax) L, (6)
where 0 < α < min{K1, log 2Amaxτ(α) , 0.1 K2γmax }.
1) Fixed step-size: Let αt = α for all t ≥ 0. For all t ≥ T1, N∑ i=1 πitE [∥∥θit − θ∗∥∥22] ≤ 2 qt N∑ i=1 πimtE [∥∥θimt − 〈θ〉mt∥∥22]+ C1(1− 0.9αγmax )t−T1 + C2
+ γmax γmin 2αζ4 t−T1∑ k=0 ηt+1−k ( 1− 0.9α γmax )k . (7)
2) Time-varying step-size: Let αt = α0t+1 with α0 ≥ γmax 0.9 . For all t ≥ LT2,
N∑ i=1 πitE [∥∥θit − θ∗∥∥22] ≤ 2 qt−T2 N∑ i=1 πiLT2+mtE [∥∥θiLT2+mt − 〈θ〉LT2+mt∥∥22]
+ C3 ( α0
qt−1 2 + αd qt−12 eL
) + 1
t
( C4 log 2 ( t α0 ) + C5 t∑ k=LT2 ηk + C6 ) . (8)
Here T1, T2,K1,K2, C1 − C6 are finite constants whose definitions are given in Appendix A.1.
Since πit is uniformly bounded below by πmin ∈ (0, 1) from Lemma 1, it is easy to see that the above bound holds for each individual E[‖θit− θ∗‖22]. To better understand the theorem, we provide the following remark.
Remark 4 In Appendix E.2.1, we show that both and (1 − 0.9αγmax ) lie in the interval (0, 1). It is easy to show that is monotonically increasing for δmax and L, monotonically decreasing for β and πmin. Also, limt→∞ ∑t−T1 k=0 ηt+1−k(1 − 0.9α γmax )k ≤ limt→∞ γmax0.9α [ηd t−T12 e + η1(1 − 0.9α γmax ) t−T1 2 ] = 0. Therefore, the summands in the finite-time bound equation 7 for the fixed step-size case are exponentially decaying except for the constant C2, which implies that lim supt→∞ ∑N i=1 π i tE[‖θit− θ∗‖22] ≤ C2, providing a constant limiting bound. From Appendix A, C2 is monotonically increasing for γmax, δmax, bmax and L, and monotonically decreasing for γmin, πmin and β. In Appendix E.2.2, we show that limt→∞ 1t ∑t k=1 ηk = 0, which implies that the finite-time bound equation 8 for the time-varying step-size case converges to zero as t → ∞. We next comment on 0.1 in the inequality defining α. Actually, we can replace 0.1 with any constant c ∈ (0, 1), which will affect the value of and the feasible set of α, with the latter becoming 0 < α < min{K1, log 2Amaxτ(α) , c K2γmax }. Thus,
the smaller the value of c is, the smaller is the feasible set of α, though the feasible set is always nonempty. For convenience, we simply pick c = 0.1 in this paper; that is why we also have 0.9 in equation 7. Lastly, we comment on α0 in the time-varying step-size case. We set α0 ≥ γmax0.9 for the purpose of getting a cleaner expression of the finite-time bound. For α0 < γmax0.9 , our approach still works, but will yield a more complicated expression. The same is true for Theorem 5.
Technical Challenge and Proof Sketch As described in the introduction, the key challenge of analyzing the finite-time performance of the distributed stochastic approximation equation 1 lies in the condition that the consensus-based interaction matrix is time-varying and stochastic (not necessarily doubly stochastic). To tackle this, we appeal to the absolute probability sequence πt of the time-varying interaction matrix sequence and introduce the quadratic Lyapunov comparison function ∑N i=1 π i tE[‖θit − θ∗‖22]. Then, using the inequality ∑N i=1 π i tE[‖θit − θ∗‖22] ≤
2 ∑N i=1 π
i tE[‖θit − 〈θ〉t‖22] + 2E[‖〈θ〉t − θ∗‖22], the next step is to find the finite-time bounds of∑N
i=1 π i tE[‖θit−〈θ〉t‖22] and E[‖〈θ〉t−θ∗‖22], respectively. The latter term is essentially the “singleagent” mean-square error. Our main analysis contribution here is to bound the former term for both fixed and time-varying step-size cases.

heading: 3 PUSH-SA

text:
The preceding section shows that the limiting state of consensus-based distributed stochastic approximation depends on π∞, which leads to a convex combination of the local equilibria of all the agents in the absence of communication, but the convex combination is in general “uncontrollable”. Note that this convex combination will correspond to a convex combination of the network-wise accumulative rewards in applications such as distributed TD learning. In an important case when the convex combination is desired to be the straight average, the existing literature e.g. Doan et al. (2019; 2021) relies on doubly stochastic matrices whose corresponding π∞ = (1/N)1N . As mentioned in the introduction, doubly stochastic matrices implicitly require bi-directional communication between any pair of neighboring agents; see e.g. gossiping (Boyd et al., 2006) and the Metropolis algorithm (Xiao et al., 2005). A popular method to achieve the straight average target while allowing uni-directional communication between neighboring agents is to appeal to the idea so-called “pushsum” (Kempe et al., 2003), which was tailored for solving the distributed averaging problem over directed graphs and has been applied to distributed optimization (Nedić & Olshevsky, 2014). In this section, we will propose a push-based distributed stochastic approximation algorithm tailored for uni-directional communication and establish its finite-time error bound.
Each agent i has control over three variables, namely yit, θ̃ i t and θ i t, in which y i t is scalar-valued with initial value 1, θ̃it can be arbitrarily initialized, and θ i 0 = θ̃ i 0. At each time t ≥ 0, each agent i sends its weighted current values ŵjit y i t and ŵ ji t (θ̃ i t + αtA(Xt)θt + αtb
i(Xt)) to each of its current out-neighbors j ∈ N i−t , and updates its variables as follows: yit+1 = ∑ j∈N it ŵijt y j t , y i 0 = 1, θ̃it+1 = ∑ j∈N it ŵijt [ θ̃jt + αt ( A(Xt)θ j t + b j(Xt) )] ,
θit+1 = θ̃it+1 yit+1 , θi0 = θ̃ i 0,
(9)
where ŵijt = 1/|N j− t |. It is worth noting that the algorithm is distributed yet requires that each agent be aware of the number of its out-neighbors.
Asymptotic performance of equation 9 with any uniformly strongly connected neighbor graph sequence is characterized by the following theorem.
Theorem 4 Suppose that Assumptions 2–5 hold. Let {θit}, i ∈ V , be generated by equation 9 and θ∗ be the unique equilibrium point of the ODE
θ̇ = Aθ + 1
N N∑ i=1 bi, (10)
where A and bi are defined in Assumption 2. If {Gt} is uniformly strongly connected, then θit will converge to θ∗ in mean square for all i ∈ V .
In this section, we define 〈θ̃〉t = 1N ∑N i=1 θ̃ i t and 〈θ〉t = 1N ∑N i=1 θ i t. To help understand these definitions, let Ŵt be the N × N matrix whose ij-th entry equals ŵijt if j ∈ N it , otherwise equals zero. It is easy to see that each Ŵt is a column stochastic matrix whose diagonal entries are all positive. Then, πt = 1N 1N for all t ≥ 0 can be regarded as an absolute probability sequence of {Ŵt}. Thus, the above two definitions are intuitively consistent with 〈θ〉t in the previous section. Finite-time performance of equation 9 with any uniformly strongly connected neighbor graph sequence is characterized by the following theorem.
Let µt = ‖A(Xt)(〈θ〉t − 〈θ̃〉t)‖2. In Appendix E.3, we show that ‖〈θ〉t − 〈θ̃〉t‖2 converges to zero as t→∞, so does µt.
Theorem 5 Suppose that Assumptions 2–4 hold and {Gt} is uniformly strongly connected by subsequences of length L. Let {θit}, i ∈ V , be generated by equation 9 with αt = α0t+1 and α0 ≥ γmax 0.9 . Then, there exists a nonnegative ̄ ≤ (1− 1 NNL ) 1 L such that for all t ≥ T̄ ,
N∑ i=1 E [∥∥θit+1 − θ∗∥∥22] ≤ C7̄t + C8 (α0̄ t2 + αd t2 e)+ C9αt
+ 1
t
( C10 log 2 ( t α0 ) + C11 t∑ k=T̄ µk + C12 ) , (11)
where T̄ and C7 − C12 are finite constants whose definitions are given in Appendix A.2.
In Appendix E.3, we show that limt→∞ 1t ∑t k=1 µk = 0, which implies that the finite-time bound equation 11 converges to zero as t→∞. It is worth mentioning that the theorem does not consider the fixed step-size case, as our current analysis approach cannot be directly applied for this case.
Proof Sketch and Technical Challenge Using the inequality ∑N i=1 E[‖θit+1 − θ∗‖22] ≤
2 ∑N i=1 E[‖θit+1 − 〈θ̃〉t‖22] + 2NE[‖〈θ̃〉t − θ∗‖22], our goal is to derive the finite-time bounds of∑N
i=1 E[‖θit+1−〈θ̃〉t‖22] and E[‖〈θ̃〉t− θ∗‖22], respectively. Although this looks similar to the proof of Theorem 3, the derivation is quite different. First, the iteration of 〈θ̃〉t is a single-agent SA plus a disturbance term 〈θ〉t − 〈θ̃〉t, so we cannot directly apply the existing single-agent SA finitetime analyses to bound E[‖〈θ̃〉t − θ∗‖22]; instead, we have to show that 〈θ〉t − 〈θ̃〉t will diminish and quantify the diminishing “speed”. Second, both the proof of showing diminishing 〈θ〉t − 〈θ̃〉t and derivation of bounding ∑N i=1 E[‖θit+1 − 〈θ̃〉t‖22] involve a key challenge: to prove the sequence {θit} generated from the Push-SA equation 9 is bounded almost surely. To tackle this, we introduce a novel way to constructing an absolute probability sequence for the Push-SA as follows. From equation 9, θit+1 = ∑N j=1 w̃ ij t [θ j t + αtA(Xt)
θjt yjt + αt bj(Xt) yjt ], where w̃ijt = (ŵ ij t y j t )/(
∑N k=1 ŵ ik t y k t ).
We show that each matrix W̃t = [w̃ ij t ] is stochastic, and there exists a unique absolute probability sequence {π̃t} for the matrix sequence {W̃t} such that π̃it ≥ π̃min for all i ∈ V and t ≥ 0, with the constant π̃min ∈ (0, 1). Most importantly, we show two critical properties of {W̃t} and {π̃t}, namely limt→∞(Πts=0W̃s) = 1 N 1N1 > N and π̃it yit
= 1N for all i, j ∈ V and t ≥ 0, which have never been reported in the literature though push-sum based algorithms have been extensively studied.

heading: 4 CONCLUDING REMARKS

text: In this paper, we have established both asymptotic and non-asymptotic analyses for a consensusbased distributed linear stochastic approximation algorithm over uniformly strongly connected graphs, and proposed a push-based variant for coping with uni-directional communication. Both algorithms and their analyses can be directly applied to TD learning. One limitation of our finitetime bounds is that they involve quite a few constants which are well defined and characterized but whose values are not easy to compute. Future directions include leveraging the analyses for resilience in the presence of malicious agents and extending the tools to more complicated RL.