{'fraction_non_alphanumeric': 0.0467893331802394, 'fraction_numerical': 0.01541464534833654, 'mean_word_length': 4.120223398001176, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 23, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Cooperative Multi-Agent Reinforcement Learning with Partial Observations

In this paper, we propose a distributed zeroth-order policy optimization method for Multi-Agent Reinforcement Learning (MARL). Existing MARL algorithms often assume that every agent can observe the states and actions of all the other agents in the network. This can be impractical in large-scale problems, where sharing the state and action information with multi-hop neighbors may incur significant communication overhead. The advantage of the proposed zeroth-order policy optimization method is that it allows the agents to compute the local policy gradients needed to update their local policy functions using local estimates of the global accumulated rewards that depend on partial state and action information only and can be obtained using consensus. Specifically, to calculate the local policy gradients, we develop a new distributed zeroth-order policy gradient estimator that relies on one-point residual-feedback which, compared to existing zeroth-order estimators that also rely on one-point feedback, significantly reduces the variance of the policy gradient estimates improving, in this way, the learning performance. We show that the proposed distributed zeroth-order policy optimization method with constant stepsize converges to a neighborhood of the global optimal policy that depends on the number of consensus steps used to calculate the local estimates of the global accumulated rewards. Moreover, we provide numerical experiments that demonstrate that our new zeroth-order policy gradient estimator is more sample-efficient compared to other existing one-point estimators.


Introduction
Multi-Agent Reinforcement Learning (MARL) has received a lot of attention in recent years due to its wide applicability in real-world large-scale decision making problems, e.g., cloud autonomous driving, distributed multi-robot planning, and distributed resource allocation, to name a few. The goal is to enable a team of agents to collaboratively determine the global optimal policy that maximizes the sum of their local accumulated rewards. To do so, the agents typically need to communicate with each other in order to obtain information about the global state and action of the team. This is because their states and rewards are generally affected by the actions of their other peers. However, sharing such information can be undesirable, due to significant communication overhead or privacy concerns. Therefore, there is a great need for MARL algorithms that rely only on partial observations of the global state and action information.
A major challenge in developing cooperative MARL methods under partial observations is that the environment, as it is perceived by every individual agent, is non-stationary since it changes as a result of changes in the policies of the other agents Gupta et al. (2017). In Foerster et al. (2018); Gupta et al. (2017); Lowe et al. (2017), this challenge is addressed using a centralized Critic function that can mitigate the effect of non-stationarity in the learning process. Then, the trained policies can be executed in a decentralized way. In Omidshafiei et al. (2017), a distributed offline experience replay technique is developed to enable fully decentralized training, which requires that all agents receive a global reward at each timestep. However, when the global reward is defined as the sum of local agent rewards, as in cooperative MARL, this global reward can not be easily available to the local agents in practice. Cooperative MARL methods that maximize the sum of local rewards are considered in Suttle et al. (2019); Zhang et al. (2018); Zhang & Zavlanos (2019). These works develop fully decentralized Actor-Critic methods where the agents maintain local estimates of the global value or policy functions, that depend on the states and actions of all other agents and update those estimates until they reach consensus. Then, these local estimates of the global value or policy functions are used to compute the policy gradient estimates needed for optimization. Since these policy gradient estimates require knowledge of the global state and action information, such Actor-Critic methods can not be used for cooperative MARL with partial state and action information.
In this paper, we propose a new distributed zeroth-order estimator of the local policy gradients, which is an extension of the one-point zeroth-order gradient estimator developed in Anonymous (2020) for centralized optimization problems that estimates the gradient using the residual of the function values at two consecutive iterations. As such, it queries the function value only once at each iteration. Specifically, our proposed estimator computes the local policy gradients by locally perturbing the local agent policies, using information about the sum of local accumulated rewards that can be obtained using consensus; the sum of local accumulated rewards is global information that is not otherwise accessible to the local agents.The advantage of our proposed zeroth-order policy optimization method is that it makes it possible to estimate the local policy gradients without having access to the global Critic function, which is not available under partial state and action information.
Related work: Zeroth-order policy optimization has been considered in Fazel et al. (2018); Malik et al. (2018) for a special case of single-agent RL problems, namely, Linear Quadratic Regulation (LQR) problems. These results were extended in Li et al. (2019) for distributed LQR problems. All these works use the one-point zeroth-order policy gradient estimator proposed in Flaxman et al. (2005); Nesterov (2013), which is known to have large variance that slows down learning Duchi et al. (2015). Instead, our proposed distributed residual-feedback estimator returns policy gradient estimates with significantly lower variance which improves the learning performance. Our work is also related to distributed zeroth-order optimization methods, as in Hajinezhad & Zavlanos (2018); Sahu et al. (2018). In these works, the agents collaborate to find a decision variable that maximizes the sum of local objective functions. For this, they compute the zeroth-order gradient estimates of their local objective functions with respect to all decision variables, even those owned by other agents. However, in MARL with partial observations, the agents can not have access to all decision variables and, therefore, can only compute the zeroth-order gradient estimate of their local objective functions with respect to those partial decision variables to which they have access. Therefore, the methods in Hajinezhad & Zavlanos (2018);Sahu et al. (2018) cannot be used to solve the MARL problems considered here. Related is finally work on multi-agent game formulations of MARL problems Lanctot et al. (2017);Srinivasan et al. (2018). While these problems rely on partial state and action information, they are non-cooperative in nature since the goal of the agents is to optimize their local policies in order to maximize their local accumulated rewards, as opposed to maximizing the sum of their local accumulated rewards. As a result, in these problems, the agents converge to a Nash equilibrium point rather than an optimal policy that maximizes the global accumulated rewards.
Contributions: In this paper, we propose a new distributed zeroth-order policy optimization method for general cooperative MARL problems. Compared to the one-point policy gradient estimators in Fazel et al. (2018); Li et al. (2019);Malik et al. (2018), our proposed residual-feedback policy gradient estimator reduces the variance of the policy gradient estimates and, therefore, improves the learning performance. Compared to the centralized estimator in Anonymous (2020) that produces unbiased gradient estimates, the proposed distributed policy gradient estimator is biased due to possible consensus errors in distributedly estimating the sum of local accumulated rewards needed for the estimation of the policy gradients. We show that the proposed zeroth-order policy optimization method with constant stepsize converges to a neighborhood of the global optimal policy whose size depends on the number of consensus steps needed to control the bias in the policy gradient estimates. Moreover, we propose a value tracking method to reduce the numer of consensus steps needed to achieve a desired user-specified solution accuracy. Finally, compared to existing distributed zerothorder optimization methods, our method is the first that does not require a perturbation of all decision variables or knowledge of all local objective function values to compute the zeroth-order gradients of the local objective functions, but still converges to a stationary point of the global objective function.
The rest of the paper is organized as follows. In Section 2, we present the MARL problem under consideration and introduce preliminary results on zeroth-order optimization. In Section 3, we develop our proposed algorithm and present the convergence analysis. In Section 4, we verify the effectiveness of our algorithms using numerical experiments. In Section 5, we conclude the paper.

Preliminaries and Problem Formulation
Consider a multi-agent system consisting of N agents. The agent dynamics are governed by a Makov Decision Process (MDP) defined by a tuple (S, A, R, P, γ), where s t = [s 1,t , s 2,t , . . . , s N,t ] ∈ S and a t = [a 1,t , a 2,t , . . . , a N,t ] ∈ A denote the joint state and action spaces of the N agents at time instant t. The reward vector r = [r 1,t , r 2,t , . . . , r N,t ] ∈ R denotes the local rewards received by each agent at time t. The local reward r i,t (s t , a t , w t ) is affected by the joint state and action of all the agents in the network, and is also subject to noise w t . The transition function P (s t , a t , s t+1 ) : S × A × S → [0, 1] ∈ P denotes the probability of transitioning to state s t+1 when the agents take action a t at state s t . Let o i,t ∈ O i represent the local observation received at agent i at time t, which contains partial entries of the joint state and action vectors, s t and a t . Agent i selects its action a i,t based on the observation o i,t using its local policy function π i : O i → A i . Let π denote the joint policy function which consists of all local policy functions π i . Then, the accumulated discounted reward received by agent i is defined as , when the agents start from the state-action pair (s, a) or state s, follow the joint policy π, and apply a discount factor γ ≤ 1 to their future rewards 1 .
Our goal in this paper is to find an optimal joint policy function π * that solves the problem max π i (s 0 , a 0 )] and ρ 0 is a distribution that the initial state-action pair is sampled from. To do so, we assume that the local policy function π i is parameterized as π i (θ i,k ), where θ i,k ≤ R di is the local policy parameter during episode k. Stacking these local policy parameters into the global policy parameter vector θ ∈ R d , we can rewrite the problem we consider in this paper as Problem (1) can be solved using distributed Actor-Critic methods as in Zhang et al. (2018); Zhang & Zavlanos (2019). These methods require that all agents maintain local estimates of the global value function or the global policy function and that these local estimates are parameterized in the same way and depend on the global states and actions of all other agents. Therefore, they cannot be used for MARL with partial state and action information. Instead, in this paper, we propose a new distributed zeroth-order policy optimization method that relies on the stochastic gradient ascent update to determine optimal policy parameters θ k that solve Problem (1). The key idea that makes it possible to use partial state and action information in the update (2) is the use zeroth-order estimators∇J(θ k ) of the true policy gradient ∇J(θ k ). Zeroth-order gradient estimators have been recently proposed in Duchi et al. (2015); Gasnikov et al. (2017);Nesterov & Spokoiny (2017), and take the form where J(θ k + δu k , ξ k ) is an unbiased noisy sample of the accumulated rewards under the perturbed policy θ k + δu k , δ ∈ R is the exploration parameter, u k ∈ R d is the random exploration direction sampled independently from a standard multivariate normal distribution N (0, I d ) and I d is an identity matrix with dimension d. The estimator (3) is called a one-point estimator because it requires one policy evaluation at a single perturbed policy, θ k + δu k . On the other hand, the estimator (4) is called a two-point estimator because it requires two policy evaluations at two different perturbed policies, θ k + δu k and θ k − δu k . While the two-point estimator (4) typically produces gradient estimates with lower variance, it is difficult to use in decentralized MARL problems. This is because, evaluation of a single policy in RL typically requires many samples, which are expensive to collect especially if drawn from a physical system. The estimator (4) doubles this cost because it requires two different policy evaluations at each iteration. Moreover, in the case of, e.g., non-episodic tasks Li et al. (2019);Zhang et al. (2018), evaluating two different policies at two different episodes separately requires additional coordination between the agents which is also expensive in practice.
To address the above limitations akin to estimators (3) and (4), in this paper, we adopt the one-point residual-feedback policy gradient estimator originally proposed in Anonymous (2020). Same as the estimator (3), the estimator (5) only requires one policy evaluation at each iteration, but can use the history of policy evaluations to effectively reduce the variance of the current policy gradient estimate and, therefore, improve the learning rate.
According to Anonymous (2020); Nesterov & Spokoiny (2017), both estimators (3) and (5) provide unbiased gradient estimates of a smoothed function J δ (θ) at θ k , where J δ (θ) is defined as J δ (θ) := E u J(θ + δu) and u is subject to a standard multivariate normal distribution. Therefore, updating the policy parameter θ k as in (2) using the gradient estimates (3) or (5) will in fact converge to a stationary point of the smoothed function J δ (θ) rather than a stationary point of the value function J(θ) that may be nonsmooth. To ensure that the stationary point found by this process is meaningful for the original MARL problem, we need to define appropriate optimality conditions that additionally ensure that J δ (θ) and J(θ) are close to each other. Specifically, we consider the following optimality criterion ∇J δ (θ) 2 ≤ , and |J δ (θ) − J(θ)| ≤ J , which suggests that θ is an −stationary point of the smoothed value function J δ (θ), and that the smoothed value function J δ (θ) is J -close to the true value function J(θ). To bound the distance between the smoothed function J δ (θ) and the original value funtion J(θ) in (6), we need the following assumption on the value function J(θ).
Given Assumption 1, the following result for the smoothed value function J δ (θ) holds.
According to Lemma 2.1, to control the approximation accuracy of the smoothed function J δ (θ), the parameter δ needs to be selected appropriately. The choice of this parameter will be discussed in Section 3. Note that although the random exploration direction u k ∼ N (0, I d ) needed to evaluate the estimator (5) can be sampled in a fully decentralized way, the global value is not accessible by the local agents. In the next section, we design a new algorithm that relies on partial state and action information only to produce a fully decentralized implementation of the estimator (5).

Algorithm Design and Theoretical Analysis
In this section, we propose a fully distributed zeroth-orther policy optimization algorithm for MARL that employs the residual-feedback zeroth-order policy gradient estimator (5). Specifically, we first introduce a consensus step so that the global value J(θ k + δu k , ξ k ) in the estimator (5) can be computed locally. Given a finite number of consensus iterations, the local estimates of J(θ k +δu k , ξ k )

Algorithm 1: Distributed Residual-Feedback Zeroth-Order Policy Optimization
Input: Exploration parameter δ, stepsize α, consensus matrix W , number of consenseus steps Nc, initial policy parameter θ0, discount ratio γ, maximum number of time steps run per episode tmax, number of episodes K, and the logic variable DoTracking. 1 Set µ −1 i (Nc) = 0 for all i = 1, 2, . . . , N ; 2 for episode k = 0, 1, 2, . . . , K do 3 For agents i = 1, 2, . . . , N , let agent i sample a random exploration direction u i,k from the standard multivariate normal distribution ; 4 Let all agents implement their perturbed policy πi(θ i,k + δu i,k ) for tmax time steps and construct unbiased estimates of their local accumulated rewards For all agent i = 1, 2, . . . , N , For agents i = 1, 2, . . . , N , let agent i update its current policy parameter θ i,k by 15 end will be inexact and, therefore, the local policy gradient estimates will be biased. To control this bias, we then introduce a value tracking technique that reduces the bias at the current episode using the local estimates of J(θ k + δu k , ξ k ) from previous episodes. Finally, we provide convergence results showing that the proposed distributed zeroth-ortder policy optimization method with constant stepsize converges to a neighborhood of the global optimal policy that is controlled by the number of consensus steps during each episode. Proofs of all theoretical results that follow can be found in the supplementary materials.
Our proposed algorithm is summarized in Algorithm 1. In what follows, we also assume that the N agents form a communication graph G = (V, E), where V = {1, 2, . . . , N } is the index set of agents and E represents the set of edges. The edge (i, j) ∈ E if agents i and j ∈ N can directly send information to each other. Moreover, we define by W ∈ R N ×N a weight matrix associated with the graph G such that the entry W ij > 0 when (i, j) ∈ E and W ij = 0 otherwise. Note that the communication graph G is independent of the coupling between agents in their state transition function P(s t , a t , s t+1 ) and reward functions {r i (s t , a t )} defined in Section 2.

Distributed Residual-Feedback Zeroth-Order Policy Optimization
In this section, we describe and analyze our proposed residual-feedback zeroth-order policy optimization algorithm in the absence of value tracking, i.e., when DoTracking = False in Algorithm 1 (line 6). Specifically, at the beginning of episode k, the agents randomly perturb their current policy parameters θ k using a random exploration direction u k and conduct on-policy local policy evaluation to obtain an unbiased estimate of the local accumulated rewards  (2019) to reduce the variance of policy evaluations and, therefore, the variance of the policy gradient estimates Konda & Tsitsiklis (2000). However, when the agents only have access to local observations o i,t which contain partial entries of (s t , a t ), these methods cannot be used. Therefore, in this paper, evaluate the local policies as J i (θ k + δu k , ξ k ) = r i (1) + γr i (2) + γ 2 r i (3) + . . . , same as in REINFORCE Williams (1992). This policy evaluation method can be implemented in a fully decentralized way but is subject to large variance, which increases the variance of the zeroth-order policy gradient estimates and degrades the converegence speed of the algorithm. The residual-feedback policy gradient estimator (5) can effectively reduce this variance as we will discuss later. In what follows, we make the following assumption on the local policy value estimator.
Assumption 2. For all agents, the local policy evaluation is unbiased and subject to bounded variance.
After all agents compute unbiased local policy values J i (θ i,k , ξ k , ξ k ), they conduct N c rounds of local averaging on their local policy values {J i (θ k + δu k , ξ k )} i=1,2,...,N (lines 7, 11-13). As a result, they obtain inexact estimates µ k i (N c + 1) of the global accumulated rewards J(θ k + δu k , ξ k ). To bound this estimation error, we need the following two assumptions.
Assumption 3. The undirected communication graph G is connected and fixed for all episodes. In addition, the associated weight matrix W is doubly stochastic. That is, W 1 = 1 and W T 1 = 1. Assumption 4 can be easily satisfied when the rewards are bounded and the discount factor γ < 1. When the rewards are unbounded, Assumption 4 holds when all policy iterates are stabilizing policies Fazel et al. (2018) Then, we can show the following lemma. Lemma 3.1. Given Assumptions 3 and 4, we have that Lemma 3.1 shows that the bias in the local estimate µ k (N c ) can be controlled by choosing a large enough N c , when the local policy values are upper and lower bounded by J u and J l . Using the estimates µ k (N c ), the agents can then construct the decentralized policy gradients (7) and update their policy parameters θ i,k (line 14). This completes episode k. The decentralized residual-feedback estimator (7) can reduce the variance of the policy gradient estimates, since the value estimate of the last policy iterate µ k−1 i (N c ) can provide a baseline to compare µ k i (N c ) to. Effectively, the value estimate of the last policy iterate has an analogous variance reduction effect to the state value V π (s) that is used as a baseline for the action value Q π (s, a) in Actor-Critic methods Konda & Tsitsiklis (2000). 3 Next, we show how to select N c so that the optimality criterion (6) is satisfied.
Then, running Algorithm 1 with DoTracking = False, we have that 1 As shown in Theorem 3.2, Algorithm 1 converges to a neighborhood of the global optimal policy whose size at steady-state is equal to 2 and can be controlled by choosing the number of consensus steps N c . Moreover, the number of consensus steps N c depends not only on the user-specified accuracy level and J , but also on the range of the policy bounds J u and J l . This is because the consensus iteration at each episode is independent of those at previous episodes. Therefore, to select N c to control the estimation bias |µ k i (N c ) − J(θ k + δu k , ξ k )|, we need to select the term J u − J l in the definition of N c in Theorem 3.2 as the difference between the initial estimates J u ] that have the maximum and minimum value.

Distributed Residual-Feedback Zeroth-Order Policy Optimization with Value Tracking
As discussed before, the estimation bias |µ k i (N c ) − J(θ k + δu k , ξ k )| at episode k can be reduced using local policy estimates form previous episodes. Specifically, rather than resetting µ k i (0) = J i (θ k + δu k , ξ k ) in line 7 of Algorithm 1, we update it using the estimate µ k−1 i (N c ) from the last episode as µ k . Then, we run N c consensus iterations on µ k i (0) as before. Letμ k (m) = 1 The following lemma shows that the value tracking updates preserve the global information J(θ k + δu k , ξ k ). Lemma 3.3. Let Assumption 3 hold. Then, running Algorithm 1 with DoTracking = True, we have thatμ k (m) = J(θ k + δu k , ξ k ) = 1 N N i=1 J i (θ i,k , ξ k ), for all m = 1, 2, . . . , N c and all k.
Lemma 3.3 implies that the local estimation bias |µ k i (N c )−J(θ k +δu k , ξ k )| is equal to the consensus error |µ k i (N c ) −μ k (N c )|. Using value tracking, the bias at episode k can be controlled by the consensus steps of past episodes. This is formally shown in the following lemma. Lemma 3.4. Let Assumptions 1, 2, 3 hold and define E k µ = µ k (N c ) −μ k (N c ) . Then, running Algorithm 1 with DoTracking = True, we have that Compared to Lemma 3.1, the proposed value tracking technique makes it possible to bound the consensus error at episode k with the consensus errors from episodes k − 1 and k − 2. Furthermore, at each episode, this error is perturbed by the second order momentum of the policy gradient estimate (5) which can be controlled by choosing a small stepsize α and a large number N c . To see the benefit of this result, when the consensus errors from episodes k − 1 and k − 2 are small, value tracking needs fewer consensus iterations to achieve small consensus error at episode k. This is in contrast to the case without value tracking, where N c is selected regardless of previous consensus errors. The following result shows convergence of Algorithm 1 using value tracking. Theorem 3.5. (Learning Rate of Algorithm 1 with Value Tracking) Let Assumptions 1,2, 3 hold and define δ = . Then, running Algorithm 1 with DoTracking = True, we have In Theorem 3.5, the constant G 2 represents the uniform bound on E[ ∇ J(θ k ) 2 ] for all k = 1, 2, . . . , K. Moreover, from the bounds on N c in Theorems 3.2 and 3.5, when and J are close to 0, we obtain that N c ∼ O log( In practice, the variance of function evaluation σ 2 can be much smaller than the range of its value [J l , J u ]. Therefore, Algorithm 1 with value tracking requires fewer consensus steps per episode than without value tracking.

Experiments
In this section, we illustrate our proposed MARL algorithm on stochastic multi-agent multi-stage decision making problems. Specifically, we conduct an ablation study to demonstrate the benefits of applying the decentralized residual-feedback zeroth-order policy gradient estimate (7) and the value tracking technique separately. We consider 16 agents that are located on a 4 × 4 grid. Agent i stores resources and receives a local deman in the amount of m i (t) and d i (t) at time t. In the meantime, agent i also shares resources with its neighbors in the grid in the amount of [. . . , a ij (t), . . . ] j∈Nj , where a ij (t) ∈ [0, 1] denotes the fraction of resources agent i sends to its neighbor j at time t. The local resources and demands at agent i are defined as m where w i,t is the noise in the demand. At time t, agent i receives a local reward r i (t), such that r i (t) = 0 when m i (t) ≥ 0 and r i (t) = −m i (t) 2 when m i (t) < 0. We consider a partial observation scenario, where agent i can only observe its local resources and demands, that is, o i (t) = [m i (t), d i (t)] T . Agent i determines its actions {a ij (t)} using its local policy function π i (o i (t)). Specifically, we have that a ij = exp(z ij )/ j exp(z ij ), where z ij = 9 p=1 o i − c p 2 θ ij (p) and c p is the p-th feature parameter. We consider episodes of length T = 30, and select the discount factor as γ = 0.75. The communication graph is assumed to be a chain graph. Moreover, we select the number of consensus steps N c = 1, and show that Algorithm 1 can achieve policy improvement even in this challenging scenario. The stepsizes are selected so that the convergence speed is optimized.
First, we compare the performance of Algorithm 1 using the decentralized policy gradients (5) and (3), without value tracking. The learning progress is presented in Figure 1(a). We observe that the decentralized residual-feedback policy gradient estimator has less variance than the existing one-point policy gradient estimator and, therefore, improves faster and finds a better policy in the end of the learning. The same effect is observed in Figure 1(b), when both estimators are implemented with value tracking. This suggests that the residual-feedback zeroth-order policy gradient estimator is superior to the one-point policy gradient estimator for decentralized policy optimization problems.
Next, we demonstrate the merit of using value tracking. Specifically, we first run Algorithm 1 with the decentralized one-point policy gradient estimator (3), with and without value tracking. The difference in the performance is shown in Figure 2(a). We observe that using value tracking results in less variance and also achieves better policies. Figure 2(b) shows the results of using the residualfeedback policy gradient estimator (5) with and without value tracking. We observe that, in this case, Algorithm 1 achieves the same level of policy improvement, whether value tracking is used or not. We also test our algorithm under diminishing stepsizes, which is considered in some MARL algorithms, e.g., in Zhang et al. (2018). Specifically, we let α t = α0 t 0.5 and α 0 = 1e −3 . In this case, we observe that Algorithm 1 with residual-feedback policy gradient estimator (5) and value tracking improves the policy faster than without value tracking.

Conclusion
In this paper, we proposed a new distributed zeroth-order policy optimization method for MARL problems. Compared to existing MARL algorithms that require all the agents' states and actions to be accessible by every local agent, our algorithm can be applied even when each agent only observes partial states and actions. Specifically, we developed a new distributed residual-feedback zeroth-order estimator of the policy gradient and analyzed the effect of bias in the local policy gradient estimates on the convergence of the proposed MARL algorithm. Furthermore, we introduced a value tracking technique to reduce the number of consensus steps needed at each episode to control the bias in the estimation of the policy gradient. Finally, we provided numerical experiments on a stochastic multi-agent multi-stage decision making problem that demonstrated the effectiveness of both the decentralized residual-feedback policy gradient estimator and the value tracking technique.

Broader Impact
This paper presents a novel distributed zeroth-order policy optimization method for cooperative MARL using partial state and action information. Cooperative MARL methods with partial information can be used to solve networked decision making problems where sharing global information is often impossible or subject to privacy concerns. As such, these methods can have a profound impact on the control of a wide range of systems including robotic, cyber-physical, and IoT systems. At the same time, the proposed distributed zeroth-order optimization methods can also be used to attack black-box cyber or physical systems. Therefore, as the study in this field advances, safety concerns related to zeroth-order attacks must also be addressed.
Proof. First, we show that 1 N 1 T µ k (m) = J(θ k + δu k , ξ k ) for all m = 0, 1, . . . . Note that the consensus step µ k i (m + 1) = j∈Ni W ij µ k j (m) (line 12 in Algorithm 1) can be equivalently written in a compact form as µ k (m + 1) = W µ k (m). Therefore, we have that where the second equality is due to Assumption 3, that the matrix W is doubly stochastic. Extending equality (9) from m to 0, we obtain that 1 , for m = 1, 2, . . . . To see this, we have that where the second equality is due to Assumption 3. According to (10), we have that The first inequality is due to the definition of the induced matrix norm W − 1 N 11 T . According to Assumption 3, we have that ρ W = W − 1 N 11 T < 1. Furthermore, recalling the fact that 1 N 1 T µ k (m) = 1 N 1 T J i (θ k + δu k , ξ k ) = J(θ k + δu k , ξ k ) for m = 0, 1, . . . , we obtain that Since Plugging this inequality into the bound in (12), we complete the proof.
Proof. According to Assumption 1 and Lemma B.1, we have that the smoothed function f δ (θ) has Lipschitz gradient with the Lipschitz constant L 1,δ = √ dL0 δ . Therefore, using the inequality (6) in Nesterov & Spokoiny (2017), we obtain that Without loss of generality, we assume that each agent's local policy function π i is parameterized with θ i ∈ R di and d i = d N for all i. Then, the update (7) can be written in the compact form where ⊗ represents the kronecker product and I di is an identity matrix with dimension d i . To simplify notations, we use µ k i or µ k to denote µ k i (N c ) and µ k (N c ) respectively. Then, we equivalently rewrite equality (15) as as in the proof of Lemma 3.1. Substituting (16) into the bound in (14) and rearranging terms, we get that where g δ (θ k ) = J(θ k +δu k ,ξ k )−J(θ k−1 +δu k−1 ,ξ k−1 ) δ u k . Dividing both sides of (17) by α and taking the expectation of both sides with respect to u k and ξ k conditioned on the filtration F k−1 = σ(u t , ξ t |t ≤ k − 1), we have that This is because E[g δ (θ k )] = ∇J δ (θ k ), ∇J δ (θ k ) and diag(µ k−1 −μ k−1 1) are fixed when conditioned on the filtration F k−1 , and E[u k ] = 0. Next, we provide bounds on the second and third terms in the right hand side (RHS) of (18). Specifically, because − ∇J δ (θ k ), 1 where the third inequality is due to the fact that diag(v 1 )v 2 2 ≤ v 1 2 v 2 2 for all v 1 , v 2 ∈ R d . Furthermore, we have that where the first two inequalities are due to the fact that v 1 + v 2 2 ≤ 2 v 1 2 + 2 v 2 2 and the third inequality is due to the fact that , the fact that µ k−1 −μ k−1 1 is independent of u k and the fact that E[ u k 2 ] = d. Substituting the bounds in (19) and (20) into the bound in (18) and rearranging the terms, we get that The proof is complete.
Proof. According to (9), we have that We use mathematical induction to construct the proof. Specifically, suppose thatμ k−1 (N c ) =μ k−1 (0) = 1 N N i=1 J i (θ k−1 + δu k−1 , ξ k−1 ) holds. Then, according to line 9 in Algorithm 1, we have that . . ] T . The second equality above is due to the induction hypothesis. We have that the induction hypothesis is satisfied forμ 0 (N c ), according to line 7 in Algorithm 1. Therefore, we have shown that 1 for all k. And due to (34), we have shown thatμ k (m) = J(θ k + δu k , ξ k ) = 1 N N i=1 J i (θ k + δu k , ξ k ), for all m = 1, 2, . . . , N c and all k. The proof is complete.

E Proof of Theorem 3.5
First, we present a lemma characterizing the bound on E[(E k µ ) 2 u k 2 ].
The second inequality holds for similar reasons as those used to obtain (45). To complete the induction argument, we simply need to verify the induction hypothesis when k = 1. It is straightforward to see that E[ g δ (θ 0 ) 2 ] ≤ G 2 due to the definition of G 2 . In addition, due to the initialization step µ −1 (N c ) = 0 in line 1 in Algorithm 1, we have that E[(E −1 µ ) 2 ] ≤ E 2 µ . To satisfy the conditions E[(E 0 µ ) 2 ] ≤ E 2 µ and E[(E 0 µ ) 2 u 0 2 ] ≤ dE 2 µ , it is sufficient to run many enough consensus steps only at the first iteration of Algorithm 1, according to Lemma 3.1. To summarize, the induction hypothesis is satisfied at the first iteration of Algorithm 1 and we have shown that for all k ≥ 0, we have that E[ g δ (θ k ) 2 ] ≤ G 2 , E[(E k µ ) 2 ] ≤ E 2 µ and E[(E k µ ) 2 u k 2 ] ≤ dE 2 µ under the choice of parameters specified in Theorem 3.5.
Finally, using the uniform bounds E[(E k µ ) 2 ] ≤ E 2 µ and E[(E k µ ) 2 u k 2 ] ≤ dE 2 µ , we can follow the same procedure as in the proof of Theorem 3.2 and obtain the following optimality bound