Paper deep dive
Distributed Zeroth-Order Policy Gradient for Networked Multi-agent Reinforcement Learning from Human Feedback
Pengcheng Dai, He Wang, Dongming Wang, Jian Qin, Wenwu Yu
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 7/8/2026, 3:52:26 PM
Summary
This paper introduces a distributed zeroth-order policy gradient algorithm for networked multi-agent reinforcement learning (NMARL) that replaces explicit reward signals with human preference feedback. The method leverages spatiotemporally truncated trajectories aggregated over each agent's κ-hop neighborhood to enable fully distributed policy updates. The authors prove polynomial sample complexity convergence to an ϵ-stationary point and validate the approach in stochastic GridWorld and predator-prey environments.
Entities (8)
Relation Signals (7)
Distributed Zeroth-Order Policy Gradient Algorithm → solves → Networked Multi-agent Reinforcement Learning
confidence 96% · we develop a distributed zeroth-order policy gradient algorithm... To address this, we introduce a novel human feedback mechanism... for general NMARL
Distributed Zeroth-Order Policy Gradient Algorithm → utilizes → Human Preference Feedback
confidence 95% · agents interact over an underlying network... based solely on human preference feedback
Distributed Zeroth-Order Policy Gradient Algorithm → operatesover → Kappa-hop Neighborhood
confidence 94% · feedback received by each agent depends solely on the state-action information within its κ-hop neighborhood
Human Preference Feedback → isgeneratedfrom → Spatiotemporally Truncated Trajectories
confidence 93% · we introduce a novel human feedback mechanism based on spatiotemporally truncated trajectories
Distributed Zeroth-Order Policy Gradient Algorithm → convergesto → Epsilon-stationary Point
confidence 92% · We further rigorously establish that the proposed algorithm converges to an ϵ-stationary point with polynomial sample complexity.
Distributed Zeroth-Order Policy Gradient Algorithm → evaluatedin → Stochastic GridWorld Environment
confidence 90% · simulation results in a stochastic GridWorld environment... demonstrate that the effectiveness
Distributed Zeroth-Order Policy Gradient Algorithm → evaluatedin →
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study a networked multi-agent reinforcement learning (NMARL) problem with human feedback in an infinite-horizon setting, where agents interact over an underlying network with localized state dependencies and aim to collaboratively maximize the average discounted return. Existing approaches with preference feedback are primarily developed for single-agent settings and rely on centralized training, which limits their scalability and applicability to large-scale networked multi-agent systems. To address this, we introduce a novel human feedback mechanism based on spatiotemporally truncated trajectories, defined as $H$-horizon trajectory pairs aggregated over each agent's $\kappa$-hop neighborhood. Building on this, we develop a distributed zeroth-order policy gradient algorithm, where each agent estimates its local policy gradient using human preference feedback generated from both the current joint policy and a perturbed joint policy drawn from zero-mean Gaussian distribution. Specifically, the algorithm is fully distributed, as the feedback received by each agent depends solely on the state-action information within its $\kappa$-hop neighborhood and does not require explicit reward signals or centralized control. We further rigorously establish that the proposed algorithm converges to an $\epsilon$-stationary point with polynomial sample complexity. Finally, simulation results in a stochastic GridWorld environment and a predator-prey environment further demonstrate that the effectiveness and scalability of the proposed algorithm in achieving collaborative optimization based solely on human preference feedback.
Tags
Links
- Source: https://arxiv.org/abs/2605.15697v1
- Canonical: https://arxiv.org/abs/2605.15697v1
PDF not stored locally. Use the link above to view on the source site.
Full Text
148,167 characters extracted from source content.
Expand or collapse full text
Distributed Zeroth-Order Policy Gradient for Networked Multi-agent Reinforcement Learning from Human Feedback Pengcheng Dai Jldaipc@163.com He Wang wanghe91@seu.edu.cn Dongming Wang wdong025@ucr.edu Jian Qin qinjian@scu.edu.cn Wenwu Yu wwyu@seu.edu.cn Singapore University of Technology and Design, Singapore 487372, Singapore Southeast University, Nanjing 211189, China University of California, Riverside, CA 92521, USA Sichuan University, Chengdu, 610065, China Purple Mountain Laboratories, Nanjing 211102, China Abstract We study a networked multi-agent reinforcement learning (NMARL) problem with human feedback in an infinite-horizon setting, where agents interact over an underlying network with localized state dependencies and aim to collaboratively maximize the average discounted return. Existing approaches with preference feedback are primarily developed for single-agent settings and rely on centralized training, which limits their scalability and applicability to large-scale networked multi-agent systems. To address this, we introduce a novel human feedback mechanism based on spatiotemporally truncated trajectories, defined as H-horizon trajectory pairs aggregated over each agent’s κ-hop neighborhood. Building on this, we develop a distributed zeroth-order policy gradient algorithm, where each agent estimates its local policy gradient using human preference feedback generated from both the current joint policy and a perturbed joint policy drawn from zero-mean Gaussian distribution. Specifically, the algorithm is fully distributed, as the feedback received by each agent depends solely on the state-action information within its κ-hop neighborhood and does not require explicit reward signals or centralized control. We further rigorously establish that the proposed algorithm converges to an ϵε-stationary point with polynomial sample complexity. Finally, simulation results in a stochastic GridWorld environment and a predator-prey environment further demonstrate that the effectiveness and scalability of the proposed algorithm in achieving collaborative optimization based solely on human preference feedback. keywords: Networked multi-agent reinforcement learning, distributed zeroth-order policy gradient algorithm, ϵε-stationary convergence. †thanks: This work was supported in part by the National Key Research and Development Program of China under Grant 2022ZD0120002 and in part by the National Natural Science Foundation of China under Grant 62233004. †thanks: Corresponding author. , , , , , 1 Introduction Reinforcement learning (RL) has achieved remarkable success in a wide range of sequential decision-making problems, including smart grids (Dai et al.,, 2020; Li et al.,, 2020; Dai et al.,, 2022), intelligent transportation (Chu et al.,, 2020; Wang et al.,, 2021; Dai et al.,, 2024), wireless communications (Tan et al.,, 2021; Meng et al.,, 2020), and recommendation systems (Afsar et al.,, 2022; Lin et al.,, 2024), etc. Traditional RL methods (Sutton & Barto,, 1998; Mnih et al.,, 2015; Sha et al.,, 2022) rely on a well-defined reward signal at each time step, which is typically assumed to be known and consistent with human intentions. Table 1: Comparison with existing algorithms under networked information structures. References Our Algorithm 1 Scalable algorithms (Qu et al., 2020a, ; Qu et al., 2020b, ) Decentralized/distributed algorithms (Zhang et al.,, 2018; Dai et al.,, 2025) State-action pairs κ-hop neighbors κ-hop neighbors Global True rewards None Local Local Q-values/parameters None κ-hop neighbors 1-hop neighbors Human preferences √ × * $×$ × * $×$ However, in many real-world control and decision-making applications, the design of a high-quality reward function is highly non-trivial and often impractical. This fundamental challenge has motivated the development of preference-based reinforcement learning (PbRL) (Christiano et al.,, 2017; Wirth et al.,, 2017), where the reward signals are implicitly derived from human preferences expressed over trajectory comparisons, rather than being explicitly specified. A common instantiation of this paradigm can be described as a three-stage training pipeline. (i) Policy pre-training: the agent pre-trains a policy using standard RL techniques or behavioral cloning; (i) Reward inference: the agent collects pairwise trajectory comparisons annotated by human evaluators and trains a reward model via maximum likelihood estimation under a preference model, such as the Bradley-Terry model (Bengs et al.,, 2021); and (i) Policy optimization: the agent optimizes its policy using the learned reward model via RL algorithms such as PPO (Schulman et al.,, 2017). Despite the empirical success of this pipeline, the reward inference stage remains a bottleneck: it is sample-inefficient, susceptible to model missspecification, and difficult to evaluate without ground-truth reward signals. To address these limitations, some preference-based policy optimization methods (Rafailov et al.,, 2023; Zhang & Ying,, 2024) have been proposed to bypass the reward modeling stage and directly optimize the policy from preference feedback. In particular, DPO algorithm (Rafailov et al.,, 2023) showed that, under the Bradley-Terry preference model and a KL-regularized RL objective, the reward function can be reparameterized in terms of the policy and a reference policy, yielding a tractable loss function directly from preference data. However, its theoretical guarantees are established under a contextual bandit assumption and do not directly extend to sequential decision-making problems. For general RL problems, including stochastic state transitions or infinite state-action space, a zeroth-order policy gradient approximation method with theoretical guarantee was proposed in (Zhang & Ying,, 2024). This approach enables policy optimization directly from human preference feedback, without requiring explicit reward signals or reward model inference. While the preference-based policy optimization methods have achieved significant success in single-agent settings, many real-world tasks inherently require coordination among multiple agents operating under local observations and communication constraints, which are naturally modeled as networked multi-agent reinforcement learning (NMARL) (Qu et al., 2020a, ; Qu et al., 2020b, ). In multi-robot navigation (Huang et al.,, 2024), for instance, robots perceive only local regions and communicate solely with neighbors, yet must jointly navigate to their respective goals while avoiding inter-agent collisions. Although individual objectives such as goal reaching and collision avoidance admit straightforward definitions, the overall coordination quality that reflects trade-offs among travel efficiency, path smoothness, and inter-agent cooperation, is inherently subjective and difficult to capture through a single scalar reward. Similarly, in multi-intersection traffic signal control (Zhao et al.,, 2026), each intersection controller observes only local traffic conditions and communicates with neighboring intersections, yet the system must jointly optimize traffic flow across the entire network. The overall traffic coordination quality which involves balancing throughput, fairness across intersections, and passenger comfort, is once again difficult to quantify using a single scalar reward. As a result, human preference feedback serves as a more natural supervisory signal in such networked settings. However, the underlying networked information structure introduces additional challenges that are absent in single-agent setting, including how to properly define human preference feedback in a networked setting and how to ensure cooperative learning among agents under communication constraints. Recent works on NMARL have developed scalable actor-critic algorithms (Qu et al., 2020a, ; Qu et al., 2020b, ) and decentralized/distributed RL algorithms (Zhang et al.,, 2018; Dai et al.,, 2025) that exploit the localized interaction structure of networked systems, these methods universally assume access to true local reward signals and rely on Q-value or Q-parameter sharings among neighboring agents. As summarized in Tables 1, our objective fundamentally deviates from this paradigm: explicit reward signals are completely eliminated and substituted with human preference feedback, and the requirement for Q-value or Q-parameter sharing is concurrently removed. This distinction introduces new algorithmic and theoretical challenges that are not addressed by existing scalable or distributed RL frameworks. Specifically, three fundamental challenges must be overcome. (i) Human feedback mechanism design. In the absence of explicit reward signals, a principled feedback mechanism must be designed to enable each agent to leverage localized preference information toward the global cooperative objective, while remaining compatible with distributed execution under communication constraints; (i) Policy update under uncertain and noisy preferences. Since human feedback constitutes the sole learning signal and is inherently stochastic, and limited to sampled trajectory comparisons, trajectory pair generation strategies must be carefully designed to elicit informative preferences, and such uncertain signals must be incorporated into the policy update process in a stable and efficient manner; (i) Theoretical analysis in distributed setting. Existing convergence results for preference-based policy optimization are primarily established for single-agent, finite-horizon settings (Zhang & Ying,, 2024), and do not directly extend to NMARL, where agents access only limited neighborhood state-action information rather than global information. A new analytical framework is thus required to rigorously characterize algorithmic convergence in such distributed settings. These challenges motivate this paper to investigate a distributed preference-based policy optimization framework for general NMARL over an infinite horizon, where agents exhibit localized state-action interactions and aim to collaboratively maximize the average discounted return based solely on human preference feedback, without relying on explicit reward signals or centralized coordination. The central question addressed is: How can a provably efficient distributed preference-based method be designed for general NMARL without explicit reward signals? To address the aforementioned challenges, we introduce a novel human feedback mechanism grounded in the concept of spatiotemporally truncated trajectories. By leveraging this, we incorporate zeroth-order optimization techniques for policy updates and develop a distributed zeroth-order policy gradient algorithm. Additionally, we rigorously establish the convergence of the proposed algorithm to an ϵε-stationary point. The main contributions of this work are summarized as follows. 1. Human feedback mechanism design. We propose a novel preference feedback mechanism based on spatiotemporally truncated trajectories, defined as H-horizon trajectory pairs constructed from each agent’s κ-hop neighborhood. Each agent collects such spatiotemporally trajectories and queries human evaluators for preference signals that implicitly reflect cooperative performance within its neighborhood, while remaining fully compatible with distributed execution. 2. Policy update under uncertain and noisy preferences. In the concrete policy update process, agents independently sample Gaussian perturbations to construct a perturbed joint policy. Each agent then collects two spatiotemporally truncated trajectories under the current and perturbed policies, and elicits human preference feedback through pairwise comparisons. Each agent then uses the received signals to approximate its local policy gradient via a zeroth-order estimator, enabling fully distributed policy update without reliance on explicit reward signals or centralized coordination. 3. Theoretical analysis in distributed setting. We propose a distributed zeroth-order policy gradient algorithm for general NMARL problems, and provide rigorous theoretical guarantees for its convergence behavior. Specifically, we establish a rigorous characterization of the first-order gradient bias and variance induced by Gaussian perturbations, spatiotemporal truncation, and stochastic preference feedback. Building on this, we prove ϵε-stationary convergence of the proposed algorithm, which does not require the reward signal and is applicable to fully distributed multi-agent settings. The rest of this paper is organized as follows. Section 2 introduces the NMARL model and its related knowledge. Section 3 introduces a novel human feedback mechanism and design a distributed zeroth-order policy gradient algorithm. Section 4 provides the convergence analysis of the proposed algorithm. The performances of the proposed algorithm in a stochastic GridWorld environment and a predator-prey environment are represented in Section 5. Finally, Section 6 discusses the concluding remarks and potential directions for future work. Notations: ℝR is the set of reals and ℝNR^N denotes the N-dimensional real vector set. For any x,y∈ℝNx,y ^N, ‖x‖1\|x\|_1 and ‖x‖\|x\| represent the standard ℒ1L_1-norm and ℒ2L_2-norm of x, respectively. ‖x−y‖TV\|x-y\|_TV denotes the total variation distance between x and y. x⊤x is the transpose of x. Let Δ∈ℝ , for scalars a∈ℝa , we define trim[a|Δ]trim[a| ] as minmaxa,Δ,1−Δ \ \a, \,1- \. Similarly, for a vector ∈ℝN v ^N, trim[|Δ]trim[ v| ] denotes the vector obtained by applying the trimming operation element-wise. [⋅]E[·] denotes the expectation taken over all involved variables. 2 NMARL problem In this section, we introduce the model of the NMARL problem and its related knowledge. 2.1 The model of NMARL The NMARL problem is formally defined as ((,ℰ), (G(N,E), ii∈,ii∈,ii∈,rii∈,πii∈,γ)\S_i\_i ,\A_i\_i ,\P_i\_i ,\r_i\_i ,\ _i\_i ,γ ), where the detailed descriptions of each element are summarized as follows. Underlying network among agents: (,ℰ)G (N,E ) is an underlying network among agents, where =1,⋯,NN=\1,·s,N\ denotes the set of agents and the edge set ℰE specifies the links between them. Define i=j|eij∈ℰN_i=\j|e_ij \ as the neighborhood of agent i. For any integer κ≥1κ≥ 1, we let iκN^κ_i denote the κ-hop neighborhood of agent i, i.e., the agents whose graph distance to agent i is less than or equal to κ, including agent i itself. Let i,−jκ=iκ∖jN^κ_i,-j=N^κ_i \j\ represent the set of agent i’s κ-hop neighbors excluding agent j. Moreover, −iκ=∖iκN^κ_-i=N ^κ_i represents the set of agents other than the set iκN^κ_i. State and action: iS_i and iA_i represent a finite state space and a finite action space of agent i, respectively. si∈is_i _i and ai∈ia_i _i denote the local state and the local action of agent i, respectively. Let =(s1,⋯,sN)∈=∏i=1Ni s=(s_1,·s,s_N)∈ S= _i=1^NS_i represent the global state and =(a1,⋯,aN)∈=∏i=1Ni a=(a_1,·s,a_N)∈ A= _i=1^NA_i denote the global action. Similarly, siκ∈iκ=∏j∈iκjs_N^κ_i _N^κ_i= _j ^κ_iS_j and aiκ∈iκ=∏j∈iκja_N^κ_i _N^κ_i= _j ^κ_iA_j represent the states and actions of agent i’s κ-hop neighbors, respectively. State transition probability function: i(si′|si,ai)P_i(s _i|s_N_i,a_i) represents the state transition probability function for agent i, specifying that the subsequent state of agent i is determined by both the current states of its neighbors and its own local action. Specifically, the global state transition probability function for agents is defined as (′|,)=∏i=1Ni(si′|si,ai) P( s | s, a)= _i=1^NP_i(s _i|s_N_i,a_i). Reward functions: ri(si,ai)r_i(s_i,a_i) represents the local reward function of agent i, which is usually handcrafted by domain experts to ensure it aligns with human interests. Parameterized policy: Each agent i∈i is associated with a class of localized policies πi(ai|si,θi) _i(a_i|s_i, _i) with θi∈ℝdi _i ^d_i being the policy parameter. Let (|)=∏i=1Nπi(ai|si,θi) π_ θ( a| s)= _i=1^N _i(a_i|s_i, _i) denote the joint policy of the agents, where =(θ1⊤,⋯,θN⊤)⊤∈ℝdtot θ=(θ _1,·s,θ _N) ^d_tot represents the vector of joint policy parameter and dtot=∑i=1Ndid_tot= _i=1^Nd_i denotes the total dimensionality of the parameter space. Discount factor: γ∈(0,1)γ∈(0,1) is the discount factor. In the NMARL problem, the objective of agents is to find a joint policy parameter θ to maximize the discounted average cumulative rewards, i.e., maxJ()≜ _ θJ( θ) ∼[1N∑t=0∞∑i=1Nγtri,t|0=, _ s ρ [ 1N _t=0^∞ _i=1^Nγ^tr_i,t | s_0= s, t∼(⋅|t)], a_t _θ(·| s_t) ], (1) where t=(s1,t,⋯,sN,t) s_t=(s_1,t,·s,s_N,t) and t=(a1,t,⋯,aN,t) a_t=(a_1,t,·s,a_N,t) represent the global state and global action at time t, respectively. ri,t=ri(si,t,ai,t)r_i,t=r_i(s_i,t,a_i,t) is the local reward of agent i at time t and ρ is the distribution of the initial state 0 s_0. For the reward signal in NMARL problem, we make the following assumption. Assumption 1. There exists a constant R>0R>0 such that the instantaneous reward ri,tr_i,t of agent i∈i at time t≥0t≥ 0 satisfies |ri,t|≤R|r_i,t|≤ R. Assumption 1 gives a bounded of the instantaneous rewards of agents, which is common in RL literature (Qu et al., 2020a, ; Qu et al., 2020b, ; Zhang et al.,, 2018; Dai et al.,, 2025) and beneficial for ensuring the boundedness of the objective function and characterizing convergence errors. 2.2 Some knowledge related to NMARL In the NMARL problem (2.1), for any joint policy _θ, let Q(,)Q _θ( s, a) and Qi(,)Q _θ_i( s, a) denote the global Q-function and the local Q-function of agent i, respectively. Specifically, they can be formally expressed as Q(,)= Q _θ( s, a)= [1N∑t=0∞∑i=1Nγtri,t|0=,0=] _ _θ [ 1N _t=0^∞ _i=1^Nγ^tr_i,t | s_0= s, a_0= a ] (2) and Qi(,)= Q _θ_i( s, a)= [∑t=0∞γtri,t|0=,0=], _ _θ [ _t=0^∞γ^tr_i,t | s_0= s, a_0= a ], (3) where the global Q-function Q(,)Q _θ( s, a) denotes the discounted cumulative rewards averaged across all agents. In contrast, the local Q-function Qi(,)Q _θ_i( s, a) accounts solely for the discounted cumulative rewards associated with agent i. According to the definitions in (2)-(3), we directly have Q(,)=1N∑i=1NQi(,). Q _θ( s, a)= 1N _i=1^NQ _θ_i( s, a). (4) Define d()d _θ_ ρ( s) as the discounted state visitation distribution of ∈ s∈ S generated by the joint policy _θ, which satisfies d()=(1−γ)∑t=0∞γtPr(t=|0∼), d _θ_ ρ( s)=(1-γ) _t=0^∞γ^tPr _θ( s_t= s| s_0 ρ), (5) where Pr(t=|0∼)Pr _θ( s_t= s| s_0 ρ) is the probability of occurrence of t= s_t= s at time t under the joint policy _θ and the initial state distribution ρ. Based on Q(,)Q _θ( s, a) in (2) and d()d _θ_ ρ( s) in (5), the policy gradient of J()J( θ) with respect to θi _i is described as follows. Lemma 1. In the NMARL problem (2.1), for any joint policy _θ, the gradient of J()J( θ) with respect to θi _i is represented as ∇θiJ()= _ _iJ( θ)= 11−γ∼d,∼[Q(,) 11-γE_ s d _θ_ ρ, a _θ [Q _θ( s, a) ×∇θilogπi(ai|si,θi)]. [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0× _ _i _i(a_i|s_i, _i) ]. (6) Lemma 1 provides an expression of the policy gradient ∇θiJ() _ _iJ( θ) in the NMARL problem, which is a direct extension of (Sutton et al.,, 2000). Note that the computation of this expression heavily depends on the global Q-function, which itself requires an explicit reward model to derive. However, in various practical tasks including dialogue generation, visual aesthetic assessment, and ethical reasoning, explicit reward models are either unobtainable or difficult to define. Instead, human preference feedback is typically provided as an alternative supervisory signal. These challenges fundamentally limit the applicability of traditional reward-based RL methods in these domains. Inspired by the approaches proposed in (Rafailov et al.,, 2023; Zhang & Ying,, 2024), which utilize human preference feedback directly to train agents’ policies, we aim to develop a distributed algorithm that does not rely on explicit reward signals and is applicable to the NMARL problem. 3 Distributed zeroth-order policy gradient algorithm In this section, we introduce a novel human feedback mechanism and design a distributed zeroth-order policy gradient algorithm for the NMARL problem, which does not rely on reward signals. 3.1 A novel human feedback mechanism In the NMARL problem, each agent i∈i maintains a local trajectory of horizon length H, defined as τi=(si,h,ai,h)h=0H−1 _i=\(s_i,h,a_i,h)\_h=0^H-1. To capture both the spatial and temporal locality of agent interactions, we introduce a notion of spatiotemporally truncated trajectories: for each agent i, the spatiotemporally truncated trajectory τiκ=τjj∈iκ _N^κ_i=\ _j\_j ^κ_i aggregates the local trajectories of agents within its κ-hop neighborhood iκN^κ_i in the underlying network G, thereby truncating the global information both spatially (limited to κ-hop neighbors) and temporally (limited to horizon H). Define the cumulative reward of each trajectory τiκ _N^κ_i as r^i(τiκ)=1N∑h=0H−1γh∑j∈iκrj(sj,h,aj,h), r_i( _N^κ_i)= 1N _h=0^H-1γ^h _j ^κ_ir_j(s_j,h,a_j,h), (7) which represents the aggregated assessment of the sum of rewards of agents within agent i’s κ-hop neighborhood on the horizon H. It is worth noting that the division by N in (7) is introduced to keep consistency with the objective function (2.1). Assume that each agent i∈i has access to human feedback in the form of a one-bit preference signal oi∈0,1o_i∈\0,1\, which is elicited from a pairwise comparison between two spatiotemporally truncated trajectories τiκ,0 _N^κ_i,0 and τiκ,1 _N^κ_i,1. Specifically, the preference signal oio_i is governed by a known link function σ:ℝ→[0,1]σ:R→[0,1], which maps the cumulative reward difference between the two trajectories to the corresponding preference probability. That is, ℙ(τiκ,1≻τiκ,0)=σ(r^i(τiκ,1)−r^i(τiκ,0)), ( _N^κ_i,1 _N^κ_i,0)=σ ( r_i( _N^κ_i,1)- r_i( _N^κ_i,0) ), (8) where τiκ,1≻τiκ,0 _N^κ_i,1 _N^κ_i,0 denotes the event that human feedback favors τiκ,1 _N^κ_i,1 over τiκ,0 _N^κ_i,0. Based on (8), the human feedback oio_i is a random sample drawn from a Bernoulli distribution with ℙ(oi=1)=ℙ(τiκ,1≻τiκ,0). (o_i=1)=P( _N^κ_i,1 _N^κ_i,0). (9) Among the various preference models proposed in the literature, the Bradley-Terry model (Bengs et al.,, 2021) has emerged as the most widely adopted framework for preference-based learning. It characterizes the probability of one trajectory being preferred over another as a logistic function of the cumulative reward difference, formally expressed as follows: ℙ(τiκ,1≻τiκ,0)=11+exp(−r^i(τiκ,1)+r^i(τiκ,0)). ( _N^κ_i,1 _N^κ_i,0)= 11+ (- r_i( _N^κ_i,1)+ r_i( _N^κ_i,0) ). Beyond the Bradley-Terry model, a variety of alternative preference models have been studied in the literature, including the linear model with a linear link function, the Weibull model, the Cauchy model, and the complementary log-log model, each tailored to specific application contexts (Train,, 2009; Greene,, 2010). Remark 1. The spatiotemporally truncated trajectory mechanism differs fundamentally from single-agent PbRL (Zhang & Ying,, 2024), where preference feedback is elicited from global trajectory comparisons involving the entire system. In contrast, each agent i in the proposed mechanism elicits preference feedback from trajectory pairs (τiκ,0,τiκ,1)( _N^κ_i,0, _N^κ_i,1) collected from its κ-hop neighborhood iκN^κ_i over H-horizon. In this framework, the human evaluator of agent i observes only the state-action sequences within κ-hop neighborhood and expresses a preference without access to any numerical reward values. This localized preference feedback implicitly captures the cooperative performance within the local neighborhood, thereby promoting coordinated optimization among agents in a fully distributed manner. 3.2 Distributed algorithm designing To develop a distributed algorithm, we define the joint policy parameter of agents in the t-th iteration as t=(θ1,t⊤,⋯,θN,t⊤)⊤ θ_t=(θ _1,t,·s,θ _N,t) and introduce the following assumption governing information exchange among agents. Assumption 2. In each t-th iteration of the learning process, each agent i∈i receives a pair of spatiotemporally truncated sample trajectories (τiκ,0,τiκ,1)( _N^κ_i,0, _N^κ_i,1) generated from two distinct policies, along with the corresponding preference signal oi∈0,1o_i∈\0,1\. Under Assumption 2, each agent collects trajectory pairs from its κ-hop neighbors via the underlying network G without requiring any reward signals, based on which the policy parameters are updated through the following steps. Step 1. Perturbed joint policy: In t-th iteration, each agent i independently samples a perturbation vector vi,t∼(di,di)v_i,t (0_d_i,I_d_i), and we denote the concatenated global perturbation as t=(v1,t⊤,⋯,vN,t⊤)⊤∼(dtot,dtot) v_t=(v _1,t,·s,v _N,t) (0_d_tot,I_d_tot). The resulting perturbed joint policy is then given by t+μt π_ θ_t+μ v_t, where μ>0μ>0 denotes the perturbation distance. Step 2. Collect samples and preferences: In the t-th iteration, agents execute both the joint policy t π_ θ_t and the perturbed joint policy t+μt π_ θ_t+μ v_t over K independent trials. In each trial k∈1,⋯,Kk∈\1,·s,K\, each agent i collects a pair of spatiotemporally truncated trajectories τiκ,0t,k∼tτ^t,k_N^κ_i,0 π_ θ_t and τiκ,1t,k∼t+μtτ^t,k_N^κ_i,1 π_ θ_t+μ v_t, and submits the pair (τiκ,0t,k,τiκ,1t,k)(τ^t,k_N^κ_i,0,τ^t,k_N^κ_i,1) to M human evaluators, obtaining preference feedback (oi,1t,k,⋯,oi,Mt,k)(o^t,k_i,1,·s,o^t,k_i,M). The preference probability ℙ(τiκ,1t,k≻τiκ,0t,k)P(τ^t,k_N^κ_i,1 τ^t,k_N^κ_i,0) is then estimated by p^it,k=trim[1M∑m=1Moi,mt,k|Δ], p^t,k_i=trim [ 1M _m=1^Mo^t,k_i,m | ], (10) where Δ=minσ(−2R(1−γH)1−γ),1−σ(2R(1−γH)1−γ) = \σ(- 2R(1-γ^H)1-γ),1-σ( 2R(1-γ^H)1-γ)\ and trim[1M∑m=1Moi,mt,k|Δ]=minmax1M∑m=1Moi,mt,k,Δ,trim [ 1M _m=1^Mo^t,k_i,m| ]= \ \ 1M _m=1^Mo^t,k_i,m, \, 1−Δ1- \. This trimming operation constrains the estimated preference probability to remain bounded away from 0 and 1, which stabilizes the policy update and enhances robustness against noisy or inconsistent human annotations. Remark 2. In contrast to existing studies on preference-based learning (Zhang & Ying,, 2024), which impose a unit-norm constraint on policy perturbations in single-agent settings, our approach adopts Gaussian perturbations, where each agent i independently draws its local perturbation vi,tv_i,t from (di,di)N(0_d_i,I_d_i). This is motivated by the fact that satisfying the unit-norm constraint in a distributed manner requires global coordination among all agents to normalize the joint perturbation vector, which is incompatible with the local communication constraints of the networked system. By adopting Gaussian perturbations, each agent independently generates its local perturbation without any inter-agent coordination, making the procedure fully compatible with distributed execution. Step 3. Policy parameter update: Upon obtaining the estimated preference probabilities p^it,kk=1K\ p^t,k_i\_k=1^K, each agent i leverages the link function σ(⋅)σ(·) to construct a local estimate of the policy gradient as follows: g^i,t=1Kμ∑k=1Kσ−1(p^it,k)vi,t. g_i,t= 1Kμ _k=1^Kσ^-1( p^t,k_i)v_i,t. (11) Based on g^i,t g_i,t in (11), the policy parameter θi,t+1 _i,t+1 can be updated by θi,t+1=θi,t+αg^i,t, _i,t+1= _i,t+α g_i,t, (12) where α>0α>0 is a learning rate in policy parameter update. Following the Steps 1 to 3 outlined above, a distributed zeroth-order policy gradient algorithm is proposed in Algorithm 1. Algorithm 1 Distributed Zeroth-Order Policy Gradient Algorithm 1:Initial parameter 0 θ_0, learning rate α>0α>0, perturbed distance μ>0μ>0, horizon length H, human evaluators M, trim size Δ=minσ(−2R(1−γH)1−γ),1−σ(2R(1−γH)1−γ) = \σ(- 2R(1-γ^H)1-γ),1-σ( 2R(1-γ^H)1-γ)\; 2:for t=0,1,⋯,T−1t=0,1,·s,T-1 do 3: Each agent i∈i independently samples a local perturbation vector vi,t∼(di,di)v_i,t (0_d_i,I_d_i), forming the global perturbation t=(v1,t⊤,⋯,vN,t⊤)⊤ v_t=(v _1,t,·s,v _N,t) 4: for k=1,2,⋯,Kk=1,2,·s,K do 5: Agents execute the joint policy t π_ θ_t to generate the first joint trajectory. Subsequently, they reset the environment and execute the perturbed joint policy t+μt π_ θ_t+μ v_t to generate the second joint trajectory; 6: Each agent i∈i collects spatiotemporally truncated trajectories τiκ,0t,kτ^t,k_N^κ_i,0 and τiκ,1t,kτ^t,k_N^κ_i,1 from first joint trajectory and second joint trajectory, respectively, via the underlying network G; 7: Each agent i∈i queries M human evaluators with (τiκ,0t,k,τiκ,1t,k)(τ^t,k_N^κ_i,0,τ^t,k_N^κ_i,1) and obtain feedback (oi,1t,k,⋯,oi,Mt,k)(o^t,k_i,1,·s,o^t,k_i,M); 8: Each agent i∈i estimates preference probability as p^it,k p^t,k_i in (10); 9: end for 10: Each agent i∈i estimates its local policy gradient through (11); 11: Each agent i∈i updates its local policy parameter by (12); 12:end for 13:Output: Final policy parameter T θ_T Algorithm 1 is a distributed human preference-based algorithm specifically designed for the NMARL problem. It is worth noting that the Algorithm 1 is communication-efficient by design: perturbation sampling (see Line 2) and policy parameter update (see Lines 9-10) are performed entirely independently by each agent without any inter-agent coordination, and inter-agent communication occurs only during the trajectory collection stage (see Line 5), where each agent receives the state-action information from its κ-hop neighbors via local message passing over the underlying network G. This design significantly reduces the communication overhead for agents and enhances the scalability of the algorithm in large-scale systems. Remark 3. The online human preference feedback in the proposed Algorithm 1 is a standard abstraction in the PbRL literature (Christiano et al.,, 2017; Wirth et al.,, 2017; Zhang & Ying,, 2024). We emphasize that “human preference feedback” should not be exclusively interpreted as requiring a real-time human annotation for every trajectory pair. Rather, it encompasses general preference signals encoding human intentions, including feedback from a pre-trained preference model, thereby enabling broad applicability to networked multi-agent settings where direct reward specification is impractical. To further contextualize the computational efficiency of the proposed algorithm, we compare Algorithm 1 with the preference-based policy gradient method (i.e., PG-RLHF) in (Du et al.,, 2024). Table 2 compares the sample complexity and number of preference queries between the proposed algorithm and PG-RLHF, where T and K denote the number of policy update iterations and pairwise trajectory pairs per iteration, respectively, and M denotes the number of preference feedback queries per trajectory pair. For PG-RLHF, K1K_1, K2K_2, and T1T_1 denote the number of samples for covariance matrix update stage, the number of samples in the stochastic gradient descent stage, and the number of iterations in the inner-loop of natural policy gradient update stage, respectively. As shown in Table 2, the proposed Algorithm 1 achieves a more compact sample complexity (TK)O(TK) than (TK1+TK+TT1K2)O(TK_1+TK+T_1K_2) in PG-RLHF, as the latter requires multiple additional estimation stages. Nevertheless, the higher query complexity (TKM)O(TKM) is a natural and acceptable trade-off: by eliminating the multiple estimation stages required in PG-RLHF, the proposed algorithm exchanges additional preference queries for a simpler algorithmic structure. Table 2: Comparison of sample complexity and the number of queries between Algorithm 1 and PG-RLHF in (Du et al.,, 2024). References Algorithm 1 PG-RLHF (Du et al.,, 2024) Samples (TK)O(TK) (TK1+TK+TT1K2)O(TK_1+TK+T_1K_2) Queries (TKM)O(TKM) (TK)O(TK) Remark 4. Note that the distributed zeroth-order policy gradient estimation is adopted for two main reasons. First, as discussed above and illustrated in Table 2, it avoids reward model learning and leads to a more compact sample complexity than first-order alternatives. Second, it is naturally compatible with trajectory-level human preference feedback. Since human evaluators compare sample trajectories rather than providing step-level rewards, first-order methods that rely on per-step reward signals or Q-value estimates are not directly applicable. In contrast, zeroth-order estimation approximates the policy gradient via trajectory-level perturbations, which aligns well with pairwise preference feedback. 4 Convergence analysis of Algorithm 1 While the proposed Algorithm 1 can be viewed at a high level as extending single-agent PbRL (Zhang & Ying,, 2024) to a networked multi-agent setting (Qu et al., 2020a, ; Qu et al., 2020b, ), the analysis reveals three non-trivial technical obstacles that distinguish it from a direct combination of existing results. (i) Feedback mechanism design: unlike single-agent PbRL where references are elicited from global trajectory comparisons, the proposed spatiotemporally truncated trajectory mechanism must simultaneously be localized, informative for cooperative performance, and consistent with the global objective, which introduces a co-design challenge in the theoretical analysis that is absent in single-agent settings. (i) Gradient estimation under Gaussian perturbations: unit-norm perturbation used in single-agent PbRL (Zhang & Ying,, 2024) requires global coordination incompatible with distributed execution. The adoption of Gaussian perturbations introduces fundamentally new bias and variance sources from the interplay of spatiotemporal truncation and stochastic preference feedback, making the theoretical characterization of the gradient estimator significantly more involved than in the single-agent case. (i) Convergence analysis: unlike existing NMARL methods (Qu et al., 2020a, ; Qu et al., 2020b, ) that rely on local reward signals and Q-value sharing, establishing convergence here requires simultaneously bounding the zeroth-order estimation error, the spatiotemporal truncation bias, and the stochastic preference feedback noise within a unified analytical framework, which constitutes the primary technical difficulty of this work. In the sequel, we develop a unified convergence analysis of Algorithm 1 that simultaneously addresses all three aforementioned challenges. Before analyzing the convergence of Algorithm 1, we impose the following assumption on the link function, as adopted in (Zhang & Ying,, 2024). Assumption 3. The link function σ(⋅)σ(·) in the preference model is defined over the interval [−2R(1−γH)1−γ,2R(1−γH)1−γ][- 2R(1-γ^H)1-γ, 2R(1-γ^H)1-γ] bounded within [0,1][0,1], and is strictly monotonically increasing with σ(0)=12σ(0)= 12. The inverse link function σ−1(⋅)σ^-1(·) is LσL_σ-Lipschitz continuous on [Δ,1−Δ][ ,1- ]. Assumption 3 serves as the basis for inferring the reward difference in agent’s κ-hop neighbors from human preference probabilities, and it can be effectively fulfilled by the Bradley-Terry model. Moreover, under Assumption 3, the error incurred by preference estimation generated by link function σ(⋅)σ(·) in Algorithm 1 is characterized in the following lemma. Lemma 2. Suppose Assumption 3 holds. For any t-th iteration, k-th trial, and agent i∈i . The trajectory pairs (τiκ,0t,k,τiκ,1t,k)(τ^t,k_N^κ_i,0,τ^t,k_N^κ_i,1) that is queried from M≥2M≥ 2 human evaluators satisfy [|σ−1(p^it,k)−(r^i(τiκ,1t,k)−r^i(τiκ,0t,k))|] [ |σ^-1( p^t,k_i)- ( r_i(τ^t,k_N^κ_i,1)- r_i(τ^t,k_N^κ_i,0) ) | ] ≤ ≤ Lσ2logM+4R(1−γH)(1−γ)M2 L_σ 2 MM+ 4R(1-γ^H)(1-γ)M^2 (13) and [|σ−1(p^it,k)−(r^i(τiκ,1t,k)−r^i(τiκ,0t,k))|4] [ |σ^-1( p^t,k_i)- ( r_i(τ^t,k_N^κ_i,1)- r_i(τ^t,k_N^κ_i,0) ) |^4 ] ≤ ≤ 4Lσ4(logM)2M2+256R4(1−γH)4(1−γ)4M2. 4L^4_σ( M)^2M^2+ 256R^4(1-γ^H)^4(1-γ)^4M^2. (14) Lemma 2 quantifies the error arising from preference estimation, and a detailed proof is provided in Appendix 7.2. It shows that the reward difference estimation from human preference in (10) is accurate as long as the number of human evaluators M is large. 4.1 Auxiliary definitions and results In this subsection, we introduce several auxiliary definitions, along with the relevant assumptions and theoretical results, which serve as a foundation for the subsequent proofs. Similar to the objective function J()J( θ) defined in (2.1), we define J^i() J_i( θ) as the spatiotemporally truncated objective function associated with agent i, which can be expressed as J^i()= J_i( θ)= ∼[1N∑t=0H−1∑j∈iκγtrj,t|0=, _ s ρ [ 1N _t=0^H-1 _j ^κ_iγ^tr_j,t | s_0= s, t∼(⋅|t)], a_t _θ(·| s_t) ], (15) It should be noted that J^i() J_i( θ) depends solely on the accumulated rewards obtained from agent i’s κ-hop neighbors over H-horizon. For any joint policy π_ θ, we define ∇J()=(∇θ1J()⊤, _ θJ( θ)= ( _ _1J( θ) , ⋯,∇θNJ()⊤)⊤·s, _ _NJ( θ) ) and ∇J^i()=(∇θ1J^i()⊤,⋯, _ θ J_i( θ)= ( _ _1 J_i( θ) ,·s, ∇θNJ^i()⊤)⊤ _ _N J_i( θ) ) , and make the following assumptions, which are a set of standard assumptions commonly adopted in (Zhang & Ying,, 2024; Qu et al., 2020a, ; Qu et al., 2020b, ; Lin et al.,, 2021; Zhou et al.,, 2023; Zhang et al.,, 2022; Ying et al.,, 2023) Assumption 4. For any joint policy parameter θ, d()d _θ_ ρ( s) and ξ(,)ξ _θ_ ρ( s, a) satisfy infmin∈d()>0 _ θ _ s∈ Sd _θ_ ρ( s)>0 and infmin(,)∈×ξ(,)>0 _ θ _( s, a)∈ S× Aξ _θ_ ρ( s, a)>0, where ξ(,)ξ _θ_ ρ( s, a) is the discounted state-action visitation distribution of (,)∈×( s, a)∈ S× A and satisfies ξ(,)=d()(|). ξ _θ_ ρ( s, a)=d _θ_ ρ( s) _θ( a| s). (16) Assumption 4 is a standard condition adopted in (Zhou et al.,, 2023; Zhang et al.,, 2022), which requires that the parameterized policy explores all the states and state-action pairs with some positive probability. This assumption is commonly satisfied in finite state-action settings under sufficient exploration, for instance when a softmax policy is used and the underlying Markov decision process is ergodic. Assumption 5. For any joint policy _θ and agent i∈i , ∇θilogπi(ai|si,θi) _ _i _i(a_i|s_i, _i) exists and satisfies ∥∇θilogπi(ai|si,θi)∥≤B\| _ _i _i(a_i|s_i, _i)\|≤ B with B>0B>0 for any (si,ai)∈i×i(s_i,a_i) _i×A_i. Assumption 5 is a common requirement for convergence analysis in the field of MARL (Qu et al., 2020a, ; Qu et al., 2020b, ; Lin et al.,, 2021; Zhang et al.,, 2022; Ying et al.,, 2023). Assumption 6. For any policy parameter θ, ∇J() _ θJ( θ) and ∇J^i() _ θ J_i( θ) are both L-Lipschitz continuous in θ. Assumption 6 is standard in the convergence analysis of NMARL problems. The L-Lipschitz continuity of ∇J() _ θJ( θ) has been widely adopted in prior work (Qu et al., 2020a, ; Qu et al., 2020b, ; Ying et al.,, 2023), and its validity under the softmax policy parameterization is well-established in (Zhou et al.,, 2023; Zhang et al.,, 2022). Remark 5. The L-Lipschitz continuity of ∇J^i() _ θ J_i( θ) is consistent with Assumption 3 in (Zhang & Ying,, 2024) established for single-agent finite-horizon objective. Building on this, we further verify that ∇J^i() _ θ J_i( θ) satisfies an analogous condition in the multi-agent setting, with a detailed justification provided in Appendix 7.3. Under Assumptions 1, 4, and 5, the spatiotemporally truncated objective function J^i() J_i( θ) in (4.1) satisfies the following property. Theorem 1. Suppose Assumptions 1, 4, and 5 hold. For any agent i∈i and any policy parameters ∈ℝdtot θ ^d_tot, we have ‖∇θiJ^i()−∇θiJ()‖≤BR((H+1)γH+2γκ+1)(1−γ)2. \| _ _i J_i( θ)- _ _iJ( θ)\|≤ BR ((H+1)γ^H+2γ^κ+1 )(1-γ)^2. (17) Theorem 1 establishes an upper bound on the discrepancy between the exact policy gradient ∇θiJ() _ _iJ( θ) as defined in (1) and the policy gradient ∇θiJ^i() _ _i J_i( θ) of the spatiotemporally truncated objective function J^i() J_i( θ) in (4.1). This bound decreases exponentially with respect to the spatiotemporal truncation parameters H and κ, and the detailed proof is provided in Appendix 7.4. Recalling the objective function J^i() J_i( θ) in (4.1), for any perturbed distance μ, we define a perturbed objective function as J^iμ()=[J^i(+μ)], J^μ_i( θ)=E_ v[ J_i( θ+μ v)], (18) where v is sampled from Gaussian distribution (dtot,dtot)N(0_d_tot,I_d_tot). By the definition of J^iμ() J^μ_i( θ) in (18), we can have the following lemma. Lemma 3. Suppose Assumption 6 holds. For the perturbed objective function J^iμ() J^μ_i( θ) defined in (18), we have the following results: (i) J^iμ() J^μ_i( θ) is L-smooth and satisfies ∇J^iμ()=[1μ(J^i(+μ)−J^i())]; _ θ J^μ_i( θ)=E_ v [ 1μ ( J_i( θ+μ v)- J_i( θ) ) v ]; (19) (i) For any ∈ℝdtot θ ^d_tot, the difference in function values satisfies |J^iμ()−J^i()|≤Lμ2dtot2| J^μ_i( θ)- J_i( θ)|≤ Lμ^2d_tot2; (i) For any ∈ℝdtot θ ^d_tot, the difference in policy gradient satisfies ‖∇J^iμ()−∇J^i()‖≤Lμdtot\| _ θ J^μ_i( θ)- _ θ J_i( θ)\|≤ Lμ d_tot; (iv) For any ∈ℝdtot θ ^d_tot, the policy gradient noise satisfies [‖1μ(J^i(+μ)−J^i())‖2] _ v [ \| 1μ ( J_i( θ+μ v)- J_i( θ) ) v \|^2 ] ≤ ≤ 2dtot(dtot+2)‖∇J^i()‖2+μ2L2dtot(dtot+2)(dtot+4)2. 2d_tot(d_tot\!+\!2)\| _ θ J_i( θ)\|^2\!+\! μ^2L^2d_tot(d_tot\!+\!2)(d_tot\!+\!4)2. (20) Lemma 3 presents several important properties of the perturbed objective function J^iμ() J^μ_i( θ), with its proof detailed in Appendix 7.5. These properties will lay the groundwork for the analysis of the ϵε-stationary convergence of Algorithm 1. 4.2 First-order gradient bias and gradient noise In this subsection, we examine the first-order bias and gradient noise introduced by the estimated policy gradients g^i,ti∈\ g_i,t\_i in (11). Let ^t=(g^1,t⊤,⋯,g^N,t⊤)⊤ g_t= ( g _1,t,·s, g _N,t ) and ℱtF_t denote the σ-algebra representing the filtration up to iteration t. The first-order gradient bias and gradient noise caused by ^t g_t in the t-th iteration are respectively defined as Biast=⟨∇J(t),[∇J(t)−^t|ℱt]⟩ _t= _ θJ( θ_t),E [ _ θJ( θ_t)- g_t |F_t ] (21) and Vart=[‖^t‖2|ℱt]. _t=E[\| g_t\|^2|F_t]. (22) Here, BiastBias_t characterizes the directional bias of the estimator relative to the true gradient ∇J(t) _ θJ( θ_t), measuring the projection of the expected estimation error onto the true gradient direction. VartVar_t denotes the expected squared norm of ^t g_t conditioned on ℱtF_t, quantifying the estimator’s intrinsic variance. Based on the definitions of BiastBias_t in (21) and VartVar_t in (22), we are able to derive the following theorem. Theorem 2. Suppose Assumptions 1-6 hold. For joint policy t π_ θ_t in the t-th iteration of Algorithm 1, by selecting M≥maxe,2(R2(1−γH)2(1−γ)2Lσ2)13,exp(8R2(1−γH)2(1−γ)2Lσ2)M≥ \e,2( R^2(1-γ^H)^2(1-γ)^2L^2_σ) 13, ( 8R^2(1-γ^H)^2(1-γ)^2L^2_σ )\, we obtain: (i) The first-order gradient bias BiastBias_t satisfies Biast≤ _t≤ ∥∇J(t)∥(BRN((H+1)γH+2γκ+1)(1−γ)2⏟Biast(i) \| _ θJ( θ_t) \| ( BR N ((H+1)γ^H+2γ^κ+1 )(1-γ)^2_Bias^(i)_t +LμdtotN⏟Biast(i)+2LσdtotNμ2logM⏟Biast(i)). +\! Lμ d_totN_Bias^(i)_t\!+\! 2L_σ d_totNμ 2 MM_Bias^(i)_t ). (23) (i) The gradient noise VartVar_t satisfies Vart≤ _t≤ 12Ndtot(dtot+2)‖∇J(t)‖2⏟Vart(i) 12Nd_tot(d_tot+2)\| _ θJ( θ_t)\|^2_Var^(i)_t +12B2NR2((H+1)γH+2γκ+1)2dtot(dtot+2)(1−γ)4⏟Vart(i) + 12B^2NR^2 ((H\!+\!1)γ^H\!+\!2γ^κ\!+\!1 )^2d_tot(d_tot\!+\!2)(1\!-\!γ)^4_Var^(i)_t +3μ2L2Ndtot(dtot+2)(dtot+4)2⏟Vart(i) + 3μ^2L^2Nd_tot(d_tot+2)(d_tot+4)2_Var^(i)_t +6∑i=1N2di(di+2)Lσ2logMμ2M⏟Vart(iv) + 6 _i=1^N 2d_i(d_i+2)L^2_σ Mμ^2M_Var^(iv)_t +132∑i=1Ndi(di+2)R2μ2(1−γ)2K⏟Vart(v). + 132 _i=1^N d_i(d_i+2)R^2μ^2(1-γ)^2K_Var^(v)_t. (24) The proof of Theorem 2 is provided in Appendix 7.6. Part (i) of Theorem 2 establishes an upper bound on the first-order gradient bias BiastBias_t of the estimated policy gradient derived from human feedback, where Biast(i)Bias^(i)_t captures the error due to spatiotemporal truncation parameters κ and H, Biast(i)Bias^(i)_t reflects the policy gradient discrepancy induced by the perturbed distance μ, and Biast(i)Bias^(i)_t represents the bias in the estimated gradient g^i,t g_i,t in (11), which depends on both μ and the M preference signals collected from human evaluators. Part (i) characterizes the gradient noise VartVar_t, where Vart(i)Var^(i)_t represents the multiplicative noise inherent in zeroth-order gradient estimation. Vart(i)Var^(i)_t captures the error induced by the truncation parameters κ and H, while Vart(i)Var^(i)_t-Vart(v)Var^(v)_t are all influenced by the perturbed distance μ. In particular, Vart(iv)Var^(iv)_t additionally depends on the number of human evaluators M, reflecting the preference estimation error, and Vart(v)Var^(v)_t further depends on the number of trials K. 4.3 ϵε-stationary convergence In this subsection, we establish the theoretical guarantees of Algorithm 1 under Assumptions 1-6. Specifically, we analyze its convergence rate and characterize the sample complexity required to attain an ϵε-stationary policy. Theorem 3. Suppose Assumptions 1-6 hold. For joint policy tt=0T−1\ π_ θ_t\_t=0^T-1 generated by Algorithm 1, suppose the number of human evaluators satisfies M≥maxe,2(R2(1−γH)2(1−γ)2Lσ2)13,exp(8R2(1−γH)2(1−γ)2Lσ2)M≥ \e,2( R^2(1-γ^H)^2(1-γ)^2L^2_σ) 13, ( 8R^2(1-γ^H)^2(1-γ)^2L^2_σ ) \, and the perturbation distance μ and the learning rate α are selected as μ2=maxR(1−γ)LKNdtot,μ^2= \ R(1-γ)L KNd_tot, 3LσLlogM 3L_σL MM \ and α=112LNdtot(dtot+2)α= 112LNd_tot(d_tot+2). Then the convergence rate of Algorithm 1 satisfies: 1T∑t=0T−1[‖∇J(t)‖2] 1T _t=0^T-1E[\| _ θJ( θ_t)\|^2] = = (LNRdtot(dtot+2)(1−γ)T ( LNRd_tot(d_tot+2)(1-γ)T +B2R2N((H+1)γH+2γκ+1)2(1−γ)4 + B^2R^2N ((H+1)γ^H+2γ^κ+1 )^2(1-γ)^4 +maxLRNdtot(1−γ)K,LNdtotLσlogM). + \ LR Nd_tot(1-γ) K,LNd_totL_σ MM \ ). (25) Theorem 3 establishes the approximate stationary convergence of Algorithm 1, with the proof provided in Appendix 7.7. To interpret the result, the term LNRdtot(dtot+2)(1−γ)T LNRd_tot(d_tot+2)(1-γ)T reflects the zeroth-order gradient ascent rate, B2R2N((H+1)γH+2γκ+1)2(1−γ)4 B^2R^2N ((H+1)γ^H+2γ^κ+1 )^2(1-γ)^4 captures the approximation error due to spatiotemporal truncation parameters κ and H, LRNdtot(1−γ)K LR Nd_tot(1-γ) K accounts for the variance arising from approximating the truncated objective via empirical trajectory rewards over K trials, and LNdtotLσlogMMLNd_totL_σ MM quantifies the error incurred in estimating the population-level preference probability from M observed human feedback signals. Based on Theorem 3, we have the following corollary that characterizes the sample complexity of Algorithm 1. Corollary 1. Suppose Assumptions 1-6 hold. For every 0<ϵ<10<ε<1, when the hyper-parameters in Algorithm 1 satisfies T=(1ϵ)T=O( 1ε), κ=Ω(log1ϵ)κ= ( 1ε), H=Ω(log1ϵ)H= ( 1ε), K=(1ϵ2)K=O( 1ε^2), and M=(log1ϵ2)M=O( 1ε^2), Algorithm 1 can learn an ϵε-stationary policy. Corollary 1 reveals the sample complexity for Algorithm 1 to converge to an ϵε-stationary point. It is a direct extension of Theorem 3, so its proof is omitted. 5 Simulation In this section, we study the empirical performance of the proposed Algorithm 1 in a stochastic GridWorld environment (Zhang & Ying,, 2024; Li et al.,, 2025; Kim et al.,, 2024) as well as a predator-prey environment, both of which corroborate the theoretical results. The source code is publicly available at https://github.com/Pengcheng-Dai/DZOPG. 5.1 GridWorld environment We consider a cooperative task involving N agents within a 5×55× 5 GridWorld environment, where agents are randomly initialized and collaboratively navigate toward a common goal. The environment exhibits the following key characteristics. (i) Local observability: each agent observes only its own position and makes decisions based solely on local information; (i) Stochastic dynamics: agents select actions from a discrete set, with movement subject to stochastic noise that diminishes as neighboring agents reach the goal; (i) Distance-aware cost: agents incur a per-step penalty proportional to their distance from the goal plus a fixed time cost, with zero reward upon and after reaching the target; (iv) Neighborhood communication: a κ-hop communication range enables agents to exchange trajectory information for preference feedback. 5.1.1 NMARL setting We now formally formulate the NMARL model for this environment. State. The local state si,ts_i,t of each agent i∈=1,⋯,Ni =\1,·s,N\ at time t is defined as the 2-dimensional vector of its position in the grid. The target is a specific location within the grid, defined as s∗s_*. Action. At each time step, agent i selects an action ai,t∈i=Up,Down,Left,Right,Staya_i,t _i=\Up,Down,Left,Right,Stay\, corresponding to the directional vectors (0,1),(0,−1),(−1,0),(1,0),\(0,1),(0,-1),(-1,0),(1,0), (0,0)(0,0)\, respectively. Underlying network. Agents communicate via an underlying network (,ℰ)G(N,E). Each agent i has access to trajectory information from its κ-hop neighborhood iκN_i^κ. State transition function. The state si,t+1s_i,t+1 of agent i evolves according to the following stochastic transition function: si,t+1=si,t,ifsi,t=s∗si,t+ai,t+εi,t,otherwise, s_i,t+1= casess_i,t,&if~s_i,t=s_*\\ s_i,t+a_i,t+ _i,t,&otherwise, cases (26) where εi,t _i,t is a random perturbation drawn from (0,0),(±1,0),(0,±1)\(0,0),(± 1,0),(0,± 1)\. The perturbation distribution governing agent i’s movement depends on the number of its neighboring agents that have already reached the goal, formally defined as follows: ℙ(εi,t)=1−χi,t,ifεi,t=(0,0)χi,t4,otherwise, ( _i,t)= cases1- _i,t,&if~ _i,t=(0,0)\\ _i,t4,&otherwise, cases (27) where χi,t=χmax−(χmax−χmin)|j|sj,t=s∗,∀j∈i||i| _i,t= _ -( _ - _ ) |\j|s_j,t=s_*,∀ j _i\||N_i|, and χmax _ and χmin _ denote the maximum and minimum perturbation factors, respectively. Reward function. The instantaneous reward for agent i at time t is defined as ri,t=10,ifsi,t=s∗for the first time0,ifsi,t=s∗after the first visit−1−‖si,t−s∗‖,otherwise, r_i,t= \ array[]l10, [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0if~s_i,t=s_*~for the first time\\ 0, [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0if~s_i,t=s_*~after the first visit\\ -1-\|s_i,t-s_*\|,otherwise, array . (31) which penalizes both the time step cost −1-1 and the current distance of agent i to the goal before reaching it. Specifically, the reward for an agent is 1010 when it reaches the goal for the first time, and becomes 0 in all subsequent time steps while waiting for other agents to reach this goal. This design encourages other agents to reach the goal as quickly as possible. Optimization objective. The local policy of agent i is parameterized as a softmax policy, defined as πi(ai|si,θi)= _i(a_i|s_i, _i)= exp(θi,si,ai)∑ai′exp(θi,si,ai′), ( _i,s_i,a_i) _a _i ( _i,s_i,a _i), (32) where θi,si,ai∈ℝ _i,s_i,a_i denotes the policy parameter of agent i associated with the state-action pair (si,ai)(s_i,a_i), and θi _i is the concatenation of θi,si,ai _i,s_i,a_i over all (si,ai)∈i×i(s_i,a_i) _i×A_i. The global objective of agents is to maximize the objective function J()J( θ) in (2.1). 5.1.2 Performance of Algorithm 1 in GridWorld environment In the simulation, we set =1,2,3,4N=\1,2,3,4\ with a chain communication network 1↔2↔3↔41 2 3 4. The target position is (4,0)(4,0), and the initial positions of agents are (2,1)(2,1), (3,1)(3,1), (2,2)(2,2), and (1,0)(1,0), respectively. The action perturbation bounds are set to χmax=0.1 _max=0.1 and χmin=0.02 _min=0.02, and the discount factor is γ=0.9γ=0.9. For Algorithm 1, we configure M=1000M=1000, K=500K=500, H=20H=20, κ=1κ=1, α=0.1α=0.1, μ=0.1μ=0.1, and di=125d_i=125 for all i∈i , with the local policy parameter of each agent initialized at θi,0=125 _i,0=0_125. Figure 1: The evaluation of the performance of Algorithm 1 with M=1000M=1000, K=500K=500, H=20H=20, and κ=1κ=1. Since no existing distributed preference-based policy optimization algorithms are specifically tailored to the considered NMARL problem, we adopt the DPO algorithm (Rafailov et al.,, 2023) as a centralized preference-based baseline, and the scalable actor-critic (SAC) algorithm (Qu et al., 2020a, ) as a distributed reward-driven baseline. In addition, to provide a reference for the best achievable performance, we include the optimal solution as a benchmark. Fig. 1 illustrates the performance of the proposed Algorithm 1, along with the DPO and SAC baselines, evaluated over 5 different random seeds. The solid curve represents the average performance, while the shaded area indicates the standard deviation. It can be observed that the proposed Algorithm 1 closely approaches the optimal value, demonstrating its effectiveness in achieving collaborative optimization solely based on human preference feedback. Moreover, compared with the DPO and SAC baselines, the proposed algorithm achieves superior performance and exhibits stable convergence behavior. We note that a small performance gap between the proposed Algorithm 1 and the optimal solution still exists. This gap is primarily attributed to the distributed mechanism in the proposed algorithm, particularly the use of the truncated distance parameter κ and the finite horizon length H in the definition of the spatiotemporally truncated trajectory, which introduce an inherent approximation error. 5.1.3 Ablation studies on sampling parameters To investigate the influence of key algorithmic parameters on performance, we conduct comprehensive ablation studies on the length of trajectory H, the number of human preference queries M, and the number of trial K. All experiments are conducted with communication distance κ=1κ=1, and all results are averaged over 5 independent random seeds. Figure 2: Ablation study on the number of trajectory length H under fixed M=1000M=1000, and K=500K=500. Fig. 2 presents the performance of Algorithm 1 with fixed M=1000M=1000, K=500K=500, and varying horizon lengths H∈5,10,20H∈\5,10,20\. The results show that performance improves as H increases, yet the differences are marginal. This is primarily because agents are capable of completing the task within H=4H=4 steps, meaning that even H=5H=5 is sufficient for agents to collect enough informative trajectory data for effective policy optimization. Figure 3: Ablation study on the number of preference queries M under fixed H=10H=10 and K=500K=500. The performance of Algorithm 1 with fixed H=10H=10, K=500K=500, and varying numbers of human evaluators M∈200,600,1000M∈\200,600,1000\ is presented in Fig. 3. The results show that performance consistently improves with larger M, demonstrating the benefit of aggregating more human preference feedback in reducing estimation variance and stabilizing the learning process. Figure 4: Ablation study on the number of trial K under fixed H=10H=10 and M=1000M=1000. Fig. 4 presents the performance of Algorithm 1 with fixed H=10H=10 and M=1000M=1000 as well as varying values of K∈100,200,300,400,500K∈\100,200,300,400,500\. As illustrated in Fig. 4, an increase in K generally results in better performance, indicating that a larger number of trajectory samples contributes to the improved robustness of policy gradient estimation. Additionally, as illustrated in Figs. 3-4, Algorithm 1 exhibits greater sensitivity to K than to M. Specifically, with fixed K, varying M yields consistent but modest performance gains, whereas with fixed M, increasing K leads to more pronounced improvements. This empirical observation aligns with Theorem 3, which suggests that the error term LRNdtot(1−γ)K LR Nd_tot(1-γ) K associated with the number of trials K has a more dominant influence on convergence than the preference estimation error LNdtotLσlogMMLNd_totL_σ MM governed by M. 5.1.4 Safety-aware NMARL setting To evaluate the effectiveness of the proposed Algorithm 1 under safety considerations, we extend the GridWorld environment to include collision-avoidance penalties. Specifically, whenever agents occupy the same grid location simultaneously, a negative reward is imposed, except at the target position, to discourage unsafe collisions. This mechanism enforces a soft safety constraint that penalizes unsafe behaviors while preserving the tractability of the learning process, which is consistent with the principles of safety-aware multi-agent control. The extended environment retains the original NMARL structure described in Section 5.1.1, with the sole modification in the reward function: for each agent i at time step t, the reward is defined as ri,t=10,ifsi,t=s∗for the first time0,ifsi,t=s∗after the first visit−1−‖si,t−s∗‖,ifsi,t≠sj,t,forallj≠i−1−‖si,t−s∗‖−rcollision,otherwise, r_i,t= \ array[]l10,~if~s_i,t=s_*~for the first time\\ 0,~if~s_i,t=s_*~after the first visit\\ -1-\|s_i,t-s_*\|,~if~s_i,t≠ s_j,t,~for~all~j≠ i\\ -1-\|s_i,t-s_*\|-r_collision,~otherwise, array . (37) where rcollision>0r_collision>0 is a collision penalty coefficient. Figure 5: The evaluation of the performance of Algorithm 1 in the safety-aware GridWorld environment with M=1000M=1000, K=500K=500, H=20H=20, and κ=1κ=1. We compare the proposed Algorithm 1 against two representative baselines, DPO and SAC, with results averaged over 55 independent random seeds presented in Fig. 5. Algorithm 1 consistently outperforms both baselines and converges to the corresponding optimal solution, which demonstrates that its effectiveness and performance advantages are retained even under safety considerations. 5.2 Predator-prey environment In order to evaluate the scalability and effectiveness of the proposed Algorithm 1, we consider a more complex predator-prey environment. The environment consists of a discrete 8×88× 8 grid populated by N=20N=20 predators, Np=10N_p=10 prey, and 1010 static obstacles, where each predator is modeled as an agent. At each time step t, each agent i observes a local state si,ts_i,t consisting solely of its own position and selects an action selects a movement action ai,t∈Up,Down,Left,Right,Staya_i,t∈\Up,Down,Left,Right,Stay\, subject to grid boundaries and obstacle constraints. The reward ri,tr_i,t of agent i at time t comprises three components: (i) a fixed time penalty to encourage efficiency, (i) a shared capture reward distributed among agents that simultaneously occupy the location of a prey, and (i) a distance-based shaping term that incentivizes progress toward the nearest prey. Formally, ri,t= r_i,t= −rtime+∑p∈p,trcapturesi,t=sp|p,t| -r^time+ _p _p,t r^capture 1\s_i,t=s_p\|C_p,t| +αp(di,t−1−di,t), + _p(d_i,t-1-d_i,t), (38) where rtime>0r^time>0 is the per-step time penalty, p,tN_p,t is the set of remaining prey at time, sps_p denotes the position of prey p, p,tC_p,t is the set of agents simultaneously capturing prey p at time t, rcapture>0r^capture>0 is the capture reward, di,td_i,t denotes the distance from agent i to its nearest prey, and αp>0 _p>0 is the scaling coefficient for the distance-based shaping term. The objective of the agents is to cooperatively capture all prey as efficiently as possible, corresponding to maximizing the cumulative reward J()J( θ) defined in (2.1). 5.2.1 Performance of Algorithm 1 in predator-prey environment In the predator-prey environment, we consider N=20N=20 agents interconnected via a chain communication network 1↔2↔⋯↔201 2 ·s 20. The initial positions of the agents are (4,4),(5,7),(4,3),(1,5),(4,4),(5,3),\(4,4),(5,7),(4,3),(1,5),(4,4),(5,3), (6,4),(4,0),(7,3),(5,2),(0,5),(1,0),(5,2),(1,4),(1,0),(6,4),(4,0),(7,3),(5,2),(0,5),(1,0),(5,2),(1,4),(1,0), (2,1),(5,0),(4,4),(3,1),(6,0)(2,1),(5,0),(4,4),(3,1),(6,0)\, the prey are located at (3,2),(1,3),(7,0),(3,0),(4,5),(2,0),(7,5),(4,2),\(3,2),(1,3),(7,0),(3,0),(4,5),(2,0),(7,5),(4,2), (3,4),(3,5)(3,4),(3,5)\, and the obstacles are placed at (0,1),\(0,1), (5,4),(6,6),(7,6),(6,3),(7,4),(3,6),(2,5),(2,4),(6,5)(5,4),(6,6),(7,6),(6,3),(7,4),(3,6),(2,5),(2,4),(6,5)\. The remaining environment parameters are set as follows: the per-step time penalty rtime=1r^time=1, the capture reward rcapture=1r^capture=1, and the distance-based shaping coefficient αp=0.5 _p=0.5. Figure 6: The evaluation of the performance of Algorithm 1 in the predator-prey environment with M=200M=200, K=100K=100, H=50H=50, and κ=1κ=1. We evaluate Algorithm 1 against DPO and SAC baselines, with results shown in Fig. 6. Algorithm 1 consistently achieves superior objective values, demonstrating its scalability and effectiveness in large-scale multi-agent scenarios. Further implementation details are available at https://github.com/Pengcheng-Dai/DZOPG. 5.2.2 Ablation studies on sampling parameters Figure 7: Ablation study on the number of trial K under fixed H=50H=50 and M=200M=200 in the predator-prey environment. As established in Theorem 3 and corroborated by the GridWorld results in Fig. 4, the sampling parameter K plays a critical role in determining the performance of Algorithm 1. To further investigate this sensitivity in a more complex setting, we evaluate the proposed algorithm under varying values of K in the predator-prey environment. As shown in Fig. 7, performance improves consistently with larger K, confirming that the number of trajectory samples for gradient estimation has a significant impact on the overall learning efficiency. Figure 8: Ablation study on the number of spatial truncated distance κ in the predator-prey environment. An additional ablation study is conducted to investigate the influence of the parameter κ. As illustrated in Fig. 8, the algorithm’s performance improves with increasing κ, which aligns with the theoretical result in Theorem 3. This effect can be attributed to the fact that a larger κ enables spatiotemporally truncated trajectories to incorporate information from a greater number of agents, thereby promoting coordinated optimization among the agents. Remark 6. The parameters H and κ correspond to the temporal and spatial truncation lengths, respectively, in the proposed Algorithm 1. Intuitively, larger values of H and κ may improve algorithmic performance. However, the appropriate choice of these parameters is closely related to the characteristics of the environment. In general, H should be set greater than the minimal horizon required for agents to reach the goal, so that the collected trajectories contain sufficiently informative samples. The choice of κ is determined by the physical communication range of agents and the degree of coupling among agents in the environment. In strongly coupled multi-agent scenarios, a larger κ is preferable, as it enables spatiotemporally truncated trajectories to capture agent interactions more effectively, thus facilitating coordinated behavior among agents. 6 Conclusions This paper proposes a distributed zeroth-order policy gradient algorithm for the NMARL problem without relying on explicit reward signals. In this approach, we introduce a novel human feedback mechanism based on spatiotemporally truncated trajectories and develop a Gaussian-perturbed gradient estimator to update the policy of agents. The proposed algorithm demonstrates a provable polynomial sample complexity in achieving ϵε-stationary convergence under mild assumptions, and exhibits strong empirical performance in stochastic environments. Future work will explore several important directions. On the theoretical side, characterizing the robustness of the proposed framework to preference model misspecification and deriving misspecification-robust convergence guarantees remains an important open problem. On the application side, we will investigate the deployment of the proposed algorithm in various real-world scenarios, such as human-robot teaming in warehouse automation and collaborative industrial assembly. References Dai et al., (2020) Dai, P., Yu, W., Wen, G., & Baldi, S. (2020). Distributed reinforcement learning algorithm for dynamic economic dispatch with unknown generation cost functions. IEEE Transactions on Industrial Informatics, 16(4), 2258-2267. Li et al., (2020) Li, F., Qin, J., & Zheng, W. (2020). Distributed Q-learning-based online optimization algorithm for unit commitment and dispatch in smart grid. IEEE Transactions on Cybernetics, 50(9), 4146-4156. Dai et al., (2022) Dai, P., Yu, W., & Chen, D. (2022). Distributed Q-learning algorithm for dynamic resource allocation with unknown objective functions and application to microgrid. IEEE Transactions on Cybernetics, 52(11), 12340-12350. Chu et al., (2020) Chu, T., Wang, J., Codecà, L., & Li, Z. (2020). Multi-agent deep reinforcement learning for large-scale traffic signal control. IEEE Transactions on Intelligent Transportation Systems, 21(3), 1086-1095. Wang et al., (2021) Wang, X., Ke, L., Qiao, Z., & Chai, X. (2021). Large-scale traffic signal control using a novel multiagent reinforcement learning. IEEE Transactions on Cybernetics, 51(1), 174-187. Dai et al., (2024) Dai, P., Yu, W., Wang, H., & Jiang, J. (2024). Applications in traffic signal control: a distributed policy gradient decomposition algorithm. IEEE Transactions on Industrial Informatics, 20(2), 2762-2775. Tan et al., (2021) Tan, J., Liang, Y.-C., Zhang, L., & Feng, G. (2021). Deep reinforcement learning for joint channel selection and power control in D2D networks. IEEE Transactions on Wireless Communications, 20(2), 1363-1378. Meng et al., (2020) Meng, F., Chen, P., Wu, L., & Cheng, J. (2020). Power allocation in multiuser cellular networks: Deep reinforcement learning approaches. IEEE Transactions on Wireless Communications, 19(10), 6255-6267. Afsar et al., (2022) Afsar, M. M., Crump, T., & Far, B. (2022) Reinforcement learning based recommender systems: a survey. ACM Computing Surveys, 55(7), 1-38. Lin et al., (2024) Lin, Y., Liu, Y., Lin, F., Zou, L., Wu, P., & Zeng, W. (2024). A survey on reinforcement learning for recommender systems. IEEE Transactions on Neural Networks and Learning Systems, 35(10), 13164-13184. Sutton & Barto, (1998) Sutton, R. S., & Barto, A. G. (1998). Reinforcement Learning: An Introduction. Cambridge, MA, USA: MIT Press. Mnih et al., (2015) Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg, S., & Hassabis, D. (2015). Human-level control through deep reinforcement learning. Nature, 518(7540), 529-533. Sha et al., (2022) Sha, X., Zhang, J., You, K., Zhang, K., & Başar, T. (2022). Fully asynchronous policy evaluation in distributed reinforcement learning over networks. Automatica, 136, 110092. Christiano et al., (2017) Christiano, P. F., Leike, J., Brown, T. B., Martic, M., Legg, S., & Amodei, D. (2017). Deep reinforcement learning from human preferences. In Advances in Neural Information Processing Systems, pages 4302-4310. Wirth et al., (2017) Wirth, C., Akrour, R., Neumann, G., & Fürnkranz, J. (2017). A survey of preference-based reinforcement learning methods. Journal of Machine Learning Research, 18(136), 1-46. Bengs et al., (2021) Bengs, V., Busa-Fekete, R., Mesaoudi-Paul, A. El, & Hüllermeier, E. (2021). Preference-based online learning with dueling bandits: a survey. Journal of Machine Learning Research, 22(7), 1-108. Schulman et al., (2017) Schulman, J., Wolski, F., Dhariwal, P., Radford, A., & Klimov, O. (2017). Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347. Rafailov et al., (2023) Rafailov, R., Sharma, A., Mitchell, E., Manning, C. D., Ermon, S., & Finn, C. (2023). Direct preference optimization: your language model is secretly a reward model. In Advances in Neural Information Processing Systems, pages 53728-53741. Zhang & Ying, (2024) Zhang, Q. & Ying L. (2024). Zeroth-order policy gradient for reinforcement learning from human feedback without reward inference. arXiv preprint arXiv:2409.17401. (20) Qu, G., Wierman, A., & Li, N. (2020). Scalable reinforcement learning of localized policies for multi-agent networked systems. In Proceedings of the Conference on Learning for Dynamics and Control, pages 256-266. (21) Qu, G., Lin, Y., Wierman, A., & Li, N. (2020). Scalable multi-agent reinforcement learning for networked systems with average reward. In Advances in Neural Information Processing Systems, pages 2074-2086. Huang et al., (2024) Huang. C., Zang, W., Pinciroli, C., Li, Z. J., Banerjee, T., Su, L., & Liu, R. (2024). Reactive multi-robot navigation in outdsoor environments through uncertainty-aware active learning of human preference landscape arXiv preprint arXiv:2409.16577. Zhao et al., (2026) Zhao, C., Cahill, V., & Dusparic, I. (2026). Balancing multiple objectives in urban traffic control with reinforcement learning from AI feedback. arXiv preprint arXiv:2602.20728. Zhang et al., (2018) Zhang, K., Yang, Z., Liu, H., Zhang, T., & Başar, T. (2018). Fully decentralized multi-agent reinforcement learning with networked agents. In Proceedings of the International Conference on Machine Learning, pages 5872-5881. Dai et al., (2025) Dai, P., Mo, Y., Yu, W., & Ren, W. (2025). Distributed neural policy gradient algorithm for global convergence of networked multi-agent reinforcement learning. IEEE Transactions on Automatic Control, 70(11), 7109-7124. Sutton et al., (2000) Sutton, R. S., McAllester, D. A., Singh, S. P., & Mansour, Y. (2000). Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, pages 1057-1063. Train, (2009) Train, K. E. (2009). Discrete Choice Methods with Simulation. Cambridge, UK: Cambridge University Press. Greene, (2010) Greene, W. H. (2010). Modeling Ordered Choices: A Primer. New York, NY, USA: Cambridge University Press, 2010. Du et al., (2024) Du, Y., Winnicki, A., Dalal, G., Mannor, S., & Srikant, R. (2024). Exploration-driven policy optimization in rlhf: Theoretical insights on efficient data utilization. arXiv preprint arXiv:2402.10342. Lin et al., (2021) Lin, Y., Qu, G., Huang, L., & Wierman, A. (2021). Multi-agent reinforcement learning in stochastic networked systems. In Advances in Neural Information Processing Systems, pages 7825-7837. Zhou et al., (2023) Zhou, Z., Chen, Z., Lin, Y., & Wierman, A. (2023). Convergence rates for localized actor-critic in networked markov potential games. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, pages 2563-2573. Zhang et al., (2022) Zhang, R., Mei, J., Dai, B., Schuurmans, D., & Li, N. (2022). On the global convergence rates of decentralized softmax gradient play in markov potential games. In Advances in Neural Information Processing Systems, pages 1923-1935. Ying et al., (2023) Ying, D., Zhang, Y., Ding, Y., Koppel, A., & Lavaei, J. (2023). Scalable primal-dual actor-critic method for safe multi-agent rl with general utilities. In Advances in Neural Information Processing Systems, pages 36524-36539. Li et al., (2025) Li, W., Liu, J., & Wei, K. (2025). ϕφ-update: a class of policy update methods with policy convergence guarantee. In Proceedings of the International Conference on Learning Representations. Kim et al., (2024) Kim, D., Lee, J., Park, J., & Seo, M. (2024). How language models extrapolate outside the training data: a case study in textualized gridworld. arXiv preprint arXiv:2406.15275. Rosenthal, (1970) Rosenthal, H. P. (1970). On the subspaces of LpL_p (p>2p>2) spanned by sequences of independent random variables. Israel Journal of Mathematics, 8(3), 273-303. 7 Appendix 7.1 Preliminary Lemma For a sequence of independent random variables ζkk=1K\ _k\_k=1^K, the following Rosenthal-type inequality for the fourth moment holds. Lemma 4. Let ζkk=1K\ _k\_k=1^K be a sequence of independent random variables and Var(ζk)Var( _k) denote the variance of ζk _k. If ζkk=1K\ _k\_k=1^K satisfies: (i) [ζk]=0E[ _k]=0; (i) |ζk|≤Cζ| _k|≤ C_ζ almost surely, we can have the following result: [(∑k=1Kζk)4]≤3(∑k=1KVar(ζk))2+Cζ2∑k=1KVar(ζk). [ ( _k=1^K _k )^4 ]≤ 3 ( _k=1^KVar( _k) )^2+C_ζ^2 _k=1^KVar( _k). (39) Proof. For the sequence of independent random variables ζkk=1K\ _k\_k=1^K, we have [(∑k=1Kζk)4] [ ( _k=1^K _k )^4 ] =∑k=1K[ζk4]+6∑1≤i<j≤K[ζi2][ζj2], = _k=1^KE[ _k^4]+6\!\! _1≤ i<j≤ K\!\!E[ _i^2]E[ _j^2], (40) where the equality can be obtained by the fact that the terms with odd powers vanish due to the zero-mean property, i.e., [ζk]=0E[ _k]=0 for all 1≤k≤K1≤ k≤ K. Next, we note that ∑1≤i<j≤K[ζi2][ζj2] _1≤ i<j≤ KE[ _i^2]E[ _j^2] = = 12[(∑k=1KVar(ζk))2−∑k=1KVar(ζk)2]. 12 [ ( _k=1^KVar( _k) )^2- _k=1^KVar( _k)^2 ]. (41) Substituting (41) into (40), we obtain [(∑k=1Kζk)4] [ ( _k=1^K _k )^4 ] = = ∑k=1K[ζk4]+3(∑k=1KVar(ζk))2−3∑k=1KVar(ζk)2 _k=1^KE[ _k^4]+3 ( _k=1^KVar( _k) )^2-3 _k=1^KVar( _k)^2 ≤ ≤ 3(∑k=1KVar(ζk))2+Cζ2∑k=1KVar(ζk), 3 ( _k=1^KVar( _k) )^2+C_ζ^2 _k=1^KVar( _k), (42) where (42) uses the fact that [ζk4]≤Cζ2[ζk2]=Cζ2Var(ζk)E[ _k^4]≤ C_ζ^2E[ _k^2]=C_ζ^2Var( _k). □ This Rosenthal-type inequality for the fourth moment of independent, bounded, zero-mean random variables can be seen as a special case of the classical result in (Rosenthal,, 1970). 7.2 Proof of Lemma 2 Proof. Similar to the analysis of Lemma 2 in (Zhang & Ying,, 2024), for any δ∈(0,1)δ∈(0,1), we can easily obtain |p^it,k−ℙ(τiκ,1t,k≻τiκ,0t,k)|≤log1δM | p^t,k_i-P (τ^t,k_N^κ_i,1 τ^t,k_N^κ_i,0 ) |≤ 1δM (43) holds with probability at least 1−δ1-δ. Let ℰi,kE_i,k denote the event in (43) holds and ℰi,k∁E _i,k represent the complementary event. By Assumption 1, when the concentration event ℰi,kE_i,k does not hold, we can have that: |σ−1(p^it,k)−(r^i(τiκ,1t,k)−r^i(τiκ,0t,k))|≤4R(1−γH)1−γ. |σ^-1( p^t,k_i)- ( r_i(τ^t,k_N^κ_i,1)- r_i(τ^t,k_N^κ_i,0) ) |≤ 4R(1-γ^H)1-γ. (44) When the concentration event ℰi,kE_i,k holds, we have |σ−1(p^it,k)−(r^i(τiκ,1t,k)−r^i(τiκ,0t,k))| |σ^-1( p^t,k_i)- ( r_i(τ^t,k_N^κ_i,1)- r_i(τ^t,k_N^κ_i,0) ) | = = |σ−1(p^it,k)−σ−1(ℙ(τiκ,1t,k≻τiκ,0t,k))| |σ^-1( p^t,k_i)-σ^-1 (P(τ^t,k_N^κ_i,1 τ^t,k_N^κ_i,0) ) | (45) ≤ ≤ Lσ|p^it,k−ℙ(τiκ,1t,k≻τiκ,0t,k)| L_σ | p^t,k_i-P(τ^t,k_N^κ_i,1 τ^t,k_N^κ_i,0) | (46) ≤ ≤ Lσlog1δM, L_σ 1δM, (47) where (45) uses the fact that r^i(τiκ,1t,k)−r^i(τiκ,0t,k)=σ−1(ℙ(τiκ,1t,k≻τiκ,0t,k)) r_i(τ^t,k_N^κ_i,1)- r_i(τ^t,k_N^κ_i,0)=σ^-1 (P(τ^t,k_N^κ_i,1 τ^t,k_N^κ_i,0) ), (46) can be achieved by Assumption 3, and (47) uses the result in (43). Combining both cases and let δ=1M2δ= 1M^2, we have [|σ−1(p^it,k)−(r^i(τiκ,1t,k)−r^i(τiκ,0t,k))|] [ |σ^-1( p^t,k_i)- ( r_i(τ^t,k_N^κ_i,1)- r_i(τ^t,k_N^κ_i,0) ) | ] ≤ ≤ ℙ(ℰi,k)Lσlog1δM+ℙ(ℰi,k∁)4R(1−γH)1−γ (E_i,k)L_σ 1δM+P(E _i,k) 4R(1-γ^H)1-γ ≤ ≤ Lσ2logM+4R(1−γH)(1−γ)M2, L_σ 2 MM+ 4R(1-γ^H)(1-γ)M^2, (48) which completes the proof of (2) in Lemma 2. To prove (2), we apply a similar procedure. When the event ℰi,k∁E _i,k holds, we have |σ−1(p^it,k)−(r^i(τiκ,1t,k)−r^i(τiκ,0t,k))|4 |σ^-1( p^t,k_i)- ( r_i(τ^t,k_N^κ_i,1)- r_i(τ^t,k_N^κ_i,0) ) |^4 ≤ ≤ 256R4(1−γH)4(1−γ)4. 256R^4(1-γ^H)^4(1-γ)^4. (49) When the event ℰi,kE_i,k holds, we can employ (47) and get |σ−1(p^it,k)−(r^i(τiκ,1t,k)−r^i(τiκ,0t,k))|4≤ |σ^-1( p^t,k_i)- ( r_i(τ^t,k_N^κ_i,1)- r_i(τ^t,k_N^κ_i,0) ) |^4≤ Lσ4(log1δ)2M2. L^4_σ ( 1δ)^2M^2. (50) Combining (7.2) and (50) and let δ=1M2δ= 1M^2 again, we have [|σ−1(p^it,k)−(r^i(τiκ,1t,k)−r^i(τiκ,0t,k))|4] [ |σ^-1( p^t,k_i)- ( r_i(τ^t,k_N^κ_i,1)- r_i(τ^t,k_N^κ_i,0) ) |^4 ] ≤ ≤ 4Lσ4(logM)2M2+256R4(1−γH)4(1−γ)4M2. 4L^4_σ( M)^2M^2+ 256R^4(1-γ^H)^4(1-γ)^4M^2. □ discussion of smooth of function 7.3 Discussion of the rationality Assumption 6 Recalling the definition of the softmax policy πi(ai|si,θi) _i(a_i|s_i, _i) in (32), there exist positive constants LbsL^s_b, LgsL^s_g, and LpsL^s_p such that the joint policy =∏i=1Nπi(ai|si,θi) π_ θ= _i=1^N _i(a_i|s_i, _i) satisfies the following properties: (i) The gradient of the joint log-policy is bounded, i.e., ∥∇log(|)∥≤Lbs\| _ θ π_ θ( a| s)\|≤ L^s_b; (i) The gradient of the joint log-policy is Lipschitz, i.e., ∥∇log(|)−∇log′(|)∥≤Lgs∥−′∥\| _ θ π_ θ( a| s)- _ θ π_ θ ( a| s)\|≤ L^s_g\| θ- θ \|; (i) The joint policy is Lipschitz in total variation, i.e., ∥(⋅|)−′(⋅|)∥TV≤Lps∥−′∥\| π_ θ(·| s)- π_ θ (·| s)\|_ TV≤ L^s_p\| θ- θ \| for all ∈ s∈ S. These results follow directly from the properties of individual softmax policies. Due to space limitations, the detailed derivations are omitted. Based on the above properties, J^i() J_i( θ) in (4.1) has the following property. Proposition 1. Suppose Assumption 1 holds. For joint softmax policy _θ, ∇J^i() _ θ J_i( θ) is Lipschitz continuity. Proof. Following the definition of J^i() J_i( θ) in (4.1), we define the associated Q-function accordingly Q^i,t(t,t)= Q _θ_i,t( s_t, a_t)= [1N∑h=tH−1∑j∈iκγh−trj,h|h=t, _ _θ [ 1N _h=t^H-1 _j ^κ_i\!\!γ^h-tr_j,h | s_h= s_t, h=t]. a_h= a_t ]. (51) For a trajectory =(0,0,…,H−1,H−1) τ=( s_0, a_0,…, s_H-1, a_H-1), we define Gi()=∑t=0H−1γtQ^i,t(t,t)∇log(t|t). G _θ_i( τ)= _t=0^H-1γ^t Q_i,t _θ( s_t, a_t) _ θ _θ( a_t| s_t). (52) The policy gradient ∇J^i() _ θ J_i( θ) is then expressed as ∇J^i()=∼[Gi()]. _ θ J_i( θ)=E_ τ _θ [G _θ_i( τ) ]. (53) For any policy parameters ,′ θ, θ , we have ∇J^i()−∇J^i(′) _ θ J_i( θ)- _ θ J_i( θ ) = = ∼[Gi()−Gi′()]⏟(i) E_ τ _θ [G _θ_i( τ)-G π_ θ _i( τ) ]_(i) +∼[Gi′()]−∼′[Gi′()]⏟(i). + E_ τ π_ θ [G π_ θ _i( τ) ]-E_ τ π_ θ [G π_ θ _i( τ) ]_(i). (54) In the (i)(i)-term of (54), we use the definition of Gi()G _θ_i( τ) in (52) and have Gi()−Gi′() G _θ_i( τ)-G π_ θ _i( τ) = = ∑t=0H−1γt[(Q^i(t,t)−Q^i′(t,t))∇log′(t|t) _t=0^H-1γ^t [ ( Q _θ_i( s_t, a_t)- Q π_ θ _i( s_t, a_t) ) _ θ π_ θ ( a_t| s_t) +Q^i(t,t)(∇log(t|t)−∇log′(t|t))]. +\! Q _θ_i( s_t, a_t) ( _ θ π_ θ( a_t| s_t)\!-\! _ θ π_ θ ( a_t| s_t) ) ]. (55) For any joint policy _θ, let P(′,′|,)=(′|,)P π_ θ( s , a | s, a)= P( s | s, a) (′|′) π_ θ( a | s ). By the definition of Q^i,t(t,t) Q _θ_i,t( s_t, a_t) in (7.3), we have |Q^i(t,t)−Q^i′(t,t)| | Q _θ_i( s_t, a_t)- Q π_ θ _i( s_t, a_t) | ≤ ≤ γ∑t+1,t+1|P(t+1,t+1|t,t)Q^i(t+1,t+1) γ _ s_t+1, a_t+1 |P π_ θ( s_t+1, a_t+1| s_t, a_t) Q _θ_i( s_t+1, a_t+1) −P′(t+1,t+1|t,t)Q^i′(t+1,t+1)| -P π_ θ ( s_t+1, a_t+1| s_t, a_t) Q π_ θ _i( s_t+1, a_t+1) | ≤ ≤ γ∑t+1,t+1|P(t+1,t+1|t,t)(Q^i(t+1,t+1) γ _ s_t+1, a_t+1 |P π_ θ( s_t+1, a_t+1| s_t, a_t) ( Q _θ_i( s_t+1, a_t+1) −Q^i′(t+1,t+1)) - Q π_ θ _i( s_t+1, a_t+1) ) +(P(t+1,t+1|t,t)−P′(t+1,t+1|t,t)) + (P π_ θ( s_t+1, a_t+1| s_t, a_t)-P π_ θ ( s_t+1, a_t+1| s_t, a_t) ) ×Q^i′(t+1,t+1)| × Q π_ θ _i( s_t+1, a_t+1) | ≤ ≤ γmaxt+1,t+1|Q^i(t+1,t+1)−Q^i′(t+1,t+1)| γ _ s_t+1, a_t+1 | Q _θ_i( s_t+1, a_t+1)- Q π_ θ _i( s_t+1, a_t+1) | +γ∑t+1,t+1(t+1|t,t)|(t+1|t+1) +γ _ s_t+1, a_t+1 P( s_t+1| s_t, a_t) | π_ θ( a_t+1| s_t+1) −′(t+1|t+1)||Q^i′(t+1,t+1)| - π_ θ ( a_t+1| s_t+1) | | Q π_ θ _i( s_t+1, a_t+1) | ≤ ≤ γmaxt+1,t+1|Q^i(t+1,t+1)−Q^i′(t+1,t+1)| γ _ s_t+1, a_t+1 | Q _θ_i( s_t+1, a_t+1)- Q π_ θ _i( s_t+1, a_t+1) | +∑t+1(t+1|t,t)∥(⋅|t+1)−′(⋅|t+1)∥1 + _ s_t+1 P( s_t+1| s_t, a_t)\| π_ θ(·| s_t+1)- π_ θ (·| s_t+1)\|_1 ×∑h=t+1H−1γh−tR × _h=t+1^H-1γ^h-tR (56) ≤ ≤ γmaxt+1,t+1|Q^i(t+1,t+1)−Q^i′(t+1,t+1)| γ _ s_t+1, a_t+1 | Q _θ_i( s_t+1, a_t+1)- Q π_ θ _i( s_t+1, a_t+1) | +2γLpsR1−γ‖−′‖, + 2γ L^s_pR1-γ\| θ- θ \|, (57) where (56) uses the fact that |Q^i′(t+1,t+1)|≤∑h=t+1H−1γh−t−1R| Q π_ θ _i( s_t+1, a_t+1)|≤ _h=t+1^H-1γ^h-t-1R and (57) use ∥(⋅|t+1)−′(⋅|t+1)∥1\| π_ θ(·| s_t+1)- π_ θ (·| s_t+1)\|_1 =2∥(⋅|t+1)−′(⋅|t+1)∥TV≤2Lps∥−′∥=2\| π_ θ(·| s_t+1)- π_ θ (·| s_t+1)\|_TV≤ 2L^s_p\| θ- θ \|. Unfolding the recursion (57) until horizon H−1H-1, we obtain |Q^i(t,t)−Q^i′(t,t)|≤2LpsR(1−γ)2‖−′‖. | Q _θ_i( s_t, a_t)- Q π_ θ _i( s_t, a_t) |≤ 2L^s_pR(1-γ)^2\| θ- θ \|. (58) Substituting (58) into (55) and using properties (i)-(i) of π_ θ, we have Gi()−Gi′()≤ G _θ_i( τ)-G π_ θ _i( τ)≤ (LgsR(1−γ)2+2LbsLpsR(1−γ)3)‖−′‖. ( L^s_gR(1-γ)^2+ 2L^s_bL^s_pR(1-γ)^3 ) \| θ- θ \|. (59) For the (i)(i)-term of (54), we define Gi,t(t,t)=γtQ^i,t(t,t)∇log(t|t)G _θ_i,t( s_t, a_t)=γ^t Q_i,t _θ( s_t, a_t) _ θ _θ( a_t| s_t) and Pt(t,t)P π_ θ_t( s_t, a_t) as the probability of occurrence of (t,t)( s_t, a_t) at time t under joint policy _θ and initial state distribution ρ. Then, the (i)(i)-term of (54) can be rewritten as ∼[Gi′()]−∼′[Gi′()] _ τ π_ θ [G π_ θ _i( τ) ]-E_ τ π_ θ [G π_ θ _i( τ) ] = = ∑t=0H−1([Gi,t′(t,t)]−′[Gi,t′(t,t)]) _t=0^H-1 (E_ π_ θ[G π_ θ _i,t( s_t, a_t)]-E_ π_ θ [G π_ θ _i,t( s_t, a_t)] ) = = ∑t=0H−1∑t,t(Pt(t,t)−Pt′(t,t))Gi,t′(t,t)) _t=0^H-1 _ s_t, a_t (P π_ θ_t( s_t, a_t)-P π_ θ _t( s_t, a_t) )G π_ θ _i,t( s_t, a_t) ) ≤ ≤ ∑t=0H−12LbsR1−γ‖Pt−Pt′‖TV, _t=0^H-1 2L^s_bR1-γ\|P π_ θ_t-P π_ θ _t\|_TV, (60) where PtP π_ θ_t and Pt′P π_ θ _t are vectors composed of elements Pt(t,t)t,t\P π_ θ_t( s_t, a_t)\_ s_t, a_t and Pt′(t,t)t,t\P π_ θ _t( s_t, a_t)\_ s_t, a_t, respectively, and the last inequality follows from the fact that |Gi,t′(t,t)|≤LbsR1−γ|G π_ θ _i,t( s_t, a_t)|≤ L^s_bR1-γ. Since Pt(t,t)=∑t−1,t−1Pt−1(t−1,t−1)P(t,t|t−1,t−1)P π_ θ_t( s_t, a_t)= _ s_t-1, a_t-1P π_ θ_t-1( s_t-1, a_t-1)P π_ θ( s_t, a_t| s_t-1, a_t-1), we can derive that ‖Pt−Pt′‖TV \|P π_ θ_t-P π_ θ _t\|_TV ≤ ≤ ∥Pt−1−Pt−1′∥TV+maxt−1,t−1∥P(⋅,⋅|t−1,t−1) \|P π_ θ_t-1-P π_ θ _t-1\|_TV+ _ s_t-1, a_t-1 \|P π_ θ(·,·| s_t-1, a_t-1) −P′(⋅,⋅|t−1,t−1)∥TV -P π_ θ (·,·| s_t-1, a_t-1) \|_TV ≤ ≤ ∥Pt−1−Pt−1′∥TV+maxt∥(⋅|t)−′(⋅|t)∥TV \|P π_ θ_t-1-P π_ θ _t-1\|_TV+ _ s_t\| π_ θ(·| s_t)- π_ θ (·| s_t)\|_TV (61) ≤ ≤ ‖Pt−1−Pt−1′‖TV+Lps‖−′‖ \|P π_ θ_t-1-P π_ θ _t-1\|_TV+L^s_p\| θ- θ \| (62) ⋮ ≤ ≤ Lpst‖−′‖, L^s_pt\| θ- θ \|, (63) where (61) uses the fact that P(t,t|t−1,t−1)=(t|t−1,t−1)(t|t)P π_ θ( s_t, a_t| s_t-1, a_t-1)= P( s_t| s_t-1, a_t-1) π_ θ( a_t| s_t) and (62) uses ∥(⋅|)−′(⋅|)∥TV≤Lps∥−′∥\| π_ θ(·| s)- π_ θ (·| s)\|_ TV≤ L^s_p\| θ- θ \| for all ∈ s∈ S. Substituting (63) into (60), we further have ∼[Gi′()]−∼′[Gi′()] _ τ π_ θ [G π_ θ _i( τ) ]-E_ τ π_ θ [G π_ θ _i( τ) ] ≤ ≤ LbsLps(H−1)HR1−γ‖−′‖. L^s_bL^s_p(H-1)HR1-γ \| θ- θ \|. (64) Combining (54), (59), and (7.3), we can obtain that ∇J^i() _ θ J_i( θ) is Lipschitz continuity. □ 7.4 Proof of Theorem 1 Proof. Before formally proving this theorem, let’s first introduce some auxiliary definitions. Different to the objective function J()J( θ) in (2.1), we define J~i() J_i( θ) as the spatially truncated objective function associated with agent i, which is expressed as J~i()=∼[1N∑t=0∞∑j∈iκγtrj,t|0=,t∼(⋅|t)]. J_i( θ)=E_ s ρ [ 1N _t=0^∞ _j ^κ_iγ^tr_j,t | s_0= s, a_t _θ(·| s_t) ]. (65) By using ∇θiJ~i() _ _i J_i( θ) as the intermediate term for analyzing the errors between ∇θiJ^i() _ _i J_i( θ) and ∇θiJ() _ _iJ( θ), we have ‖∇θiJ^i()−∇θiJ()‖ \| _ _i J_i( θ)- _ _iJ( θ)\| ≤ ≤ ‖∇θiJ^i()−∇θiJ~i()‖⏟(i)+‖∇θiJ~i()−∇θiJ()‖⏟(i). \| _ _i J_i( θ)- _ _i J_i( θ)\|_(i)+ \| _ _i J_i( θ)- _ _iJ( θ)\|_(i). (66) For (i)(i)-term in (66), we revisit the Monte Carlo policy gradient formulation presented in (Sutton & Barto,, 1998) and obtain ∇θiJ~i()=t,t∼[1N∑t=0∞ _ _i J_i( θ)=E_ s_t, a_t π_ θ [ 1N _t=0^∞ ∇θilogπi(ai,t|si,t,θi)∑j∈iκ∑l=0∞γt+l _ _i _i(a_i,t|s_i,t, _i) _j ^κ_i _l=0^∞γ^t+l rj,t+l]r_j,t+l ] and ∇θiJ^i()=t,t∼[1N∑t=0H−1 _ _i J_i( θ)=E_ s_t, a_t π_ θ [ 1N _t=0^H-1 ∇θilogπi(ai,t|si,t,θi) _ _i _i(a_i,t|s_i,t, _i) ∑j∈iκ∑l=0H−1−tγt+lrj,t+l] _j ^κ_i _l=0^H-1-tγ^t+lr_j,t+l ]. Building upon these expressions, we have ‖∇θiJ^i()−∇θiJ~i()‖ \| _ _i J_i( θ)- _ _i J_i( θ)\| = = ∥t,t∼[1N∑t=0H−1∇θilogπi(ai,t|si,t,θi)∑j∈iκ \|E_ s_t, a_t π_ θ [ 1N _t=0^H-1 _ _i _i(a_i,t|s_i,t, _i) _j ^κ_i ∑l=H−t∞γt+lrj,t+l]+t,t∼[1N∑t=H∞ _l=H-t^∞γ^t+lr_j,t+l ]+E_ s_t, a_t π_ θ [ 1N _t=H^∞ ∇θilogπi(ai,t|si,t,θi)∑j∈iκ∑l=0∞γt+lrj,t+l]∥ _ _i _i(a_i,t|s_i,t, _i) _j ^κ_i _l=0^∞γ^t+lr_j,t+l ] \| ≤ ≤ ∑t=0H−1BRγH1−γ+∑t=H∞BRγt1−γ _t=0^H-1 BRγ^H1-γ+ _t=H^∞ BRγ^t1-γ (67) ≤ ≤ BR(H+1)γH(1−γ)2, BR(H+1)γ^H(1-γ)^2, (68) where (67) can be achieved by Assumption 1 and Assumption 5. For (i)(i)-term in (66), we introduce several definitions to facilitate the analysis. By using ξ(,)ξ _θ_ ρ( s, a) in (16), we further design a class of truncated Q-function as Qtru,i(siκ,aiκ) Q _θ_tru,i(s_N^κ_i,a_N^κ_i) = = ∑s−iκ,a−iκξ(s−iκ,a−iκ|siκ,aiκ) _s_N^κ_-i,a_N^κ_-iξ _θ_ ρ(s_N^κ_-i,a_N^κ_-i|s_N^κ_i,a_N^κ_i) ×Qi(siκ,s−iκ,aiκ,a−iκ), [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0×Q _θ_i(s_N^κ_i,s_N^κ_-i,a_N^κ_i,a_N^κ_-i), (69) where ξ(s−iκ,a−iκ|siκ,aiκ)ξ _θ_ ρ(s_N^κ_-i,a_N^κ_-i|s_N^κ_i,a_N^κ_i) is the weight coefficient and satisfies ξ(s−iκ,a−iκ|siκ,aiκ) ξ _θ_ ρ(s_N^κ_-i,a_N^κ_-i|s_N^κ_i,a_N^κ_i) = = ξ(siκ,s−iκ,aiκ,a−iκ)∑s−iκ′,a−iκ′ξ(siκ,s−iκ′,aiκ,a−iκ′). ξ _θ_ ρ(s_N^κ_i,s_N^κ_-i,a_N^κ_i,a_N^κ_-i) _s _N^κ_-i,a _N^κ_-iξ _θ_ ρ(s_N^κ_i,s _N^κ_-i,a_N^κ_i,a _N^κ_-i). (70) By the definition of ξ(s−iκ,a−iκ|siκ,aiκ)ξ _θ_ ρ(s_N^κ_-i,a_N^κ_-i|s_N^κ_i,a_N^κ_i) in (7.4) and Assumption 4, it is obvious that the weight coefficients in (7.4) are non-negative and satisfy ∑s−iκ′,a−iκ′ξ(s−iκ′,a−iκ′|siκ,aiκ)=1. _s _N^κ_-i,a _N^κ_-i\!\!\!\!ξ _θ_ ρ(s _N^κ_-i,a _N^κ_-i|s_N^κ_i,a_N^κ_i)=1. (71) Inspired by (Qu et al., 2020a, ), we define a truncated policy gradient of agent i as gtru,i= g _θ_tru,i= 11−γ∼d,∼[1N∑j∈iκQtru,j(sjκ,ajκ) 11-γE_ s d _θ_ ρ, a _θ [ 1N _j ^κ_iQ _θ_tru,j(s_N^κ_j,a_N^κ_j) ×∇θilogπi(ai|si,θi)], [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0× _ _i _i(a_i|s_i, _i) ], (72) and have that ‖gtru,i−∇θiJ()‖≤2BR(1−γ)2γκ+1. \|g _θ_tru,i- _ _iJ( θ)\|≤ 2BR(1-γ)^2γ^κ+1. (73) The result in (73) characterizes the approximation error between the truncated policy gradient gtru,ig _θ_tru,i and the exact policy gradient ∇θiJ() _ _iJ( θ), which can be directly obtained from Lemma 3 and Lemma 4 in (Qu et al., 2020a, ). Note that unlike (Qu et al., 2020a, ), where the reward is assumed to lie in [0,R][0,R], the reward range in Assumption 1 of this work is [−R,R][-R,R]. Consequently, the upper bound of (73) contains an additional factor of 22. For any agent i∈i , by the definition of gtru,ig _θ_tru,i in (72), we have gtru,i= g π_ θ_tru,i= 11−γ∼d,∼[1N∑j∈iκQtru,j(sjκ,ajκ) 11-γE_ s d π_ θ_ ρ, a π_ θ [ 1N _j ^κ_iQ π_ θ_tru,j(s_N^κ_j,a_N^κ_j) ×∇θilogπi(ai|si,θi)] [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0× _ _i _i(a_i|s_i, _i) ] = = 11−γ∼d,∼[1N∑j∈iκ∑s~−jκ,a~−jκ 11-γE_ s d π_ θ_ ρ, a π_ θ [ 1N _j ^κ_i _ s_N^κ_-j, a_N^κ_-j ξ(s~−jκ,a~−jκ|sjκ,ajκ) ξ π_ θ_ ρ( s_N^κ_-j, a_N^κ_-j|s_N^κ_j,a_N^κ_j) ×Qj(sjκ,s~−jκ,ajκ,a~−jκ) [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0×Q π_ θ_j(s_N^κ_j, s_N^κ_-j,a_N^κ_j, a_N^κ_-j) ×∇θilogπi(ai|si,θi,t)] [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0× _ _i _i(a_i|s_i, _i,t) ] = = 11−γ∼d,∼[1N 11-γE_ s d π_ θ_ ρ, a π_ θ [ 1N ×∑j∈iκQj(sjκ,s−jκ,ajκ,a−jκ) [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0× _j ^κ_iQ π_ θ_j(s_N^κ_j,s_N^κ_-j,a_N^κ_j,a_N^κ_-j) ×∇θilogπi(ai|si,θi)] [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0× _ _i _i(a_i|s_i, _i) ] (74) = = ∇θiJ~i(), _ _i J_i( θ), (75) where the equality (74) is obtained from the definition of ξ(s−iκ,a−iκ|siκ,aiκ)ξ _θ_ ρ(s_N^κ_-i,a_N^κ_-i|s_N^κ_i,a_N^κ_i) in (7.4) and the equality (75) uses another expression of ∇θiJ~i() _ _i J_i( θ), similar to the form of ∇θiJ() _ _iJ( θ) in (1). By combining (73) and (75), we obtain ‖∇θiJ~i()−∇θiJ()‖≤2BR(1−γ)2γκ+1 \| _ _i J_i( θ)- _ _iJ( θ)\|≤ 2BR(1-γ)^2γ^κ+1 (76) for all agent i∈i . Substituting (68) and (76) into (66), we can complete the proof. □ 7.5 Proof of Lemma 3 Proof. (i) By the definition of J^iμ() J^μ_i( θ) in (18), for any ,′∈ℝdtot θ, θ ^d_tot, we can have ‖∇J^iμ()−∇J^iμ(′)‖ \| _ θ J^μ_i( θ)- _ θ J^μ_i( θ )\| = = ∥∇[J^i((+μ)]−∇[J^i(′+μ)]∥ \| _ θE_ v[ J_i(( θ+μ v)]- _ θE_ v[ J_i( θ +μ v)] \| = = ‖[∇J^i(+μ)−∇J^i(′+μ)]‖ \|E_ v [ _ θ J_i( θ+μ v)- _ θ J_i( θ +μ v) ] \| ≤ ≤ [‖∇J^i(+μ)−∇J^i(′+μ)‖] _ v [ \| _ θ J_i( θ+μ v)- _ θ J_i( θ +μ v) \| ] (77) ≤ ≤ L‖−′‖, L\| θ- θ \|, (78) where (77) uses the triangle inequality of norm and (78) can be obtained by Assumption 6. Recalling the expression for J^iμ() J^μ_i( θ) in (18), we can have ∇J^iμ()= _ θ J^μ_i( θ)= ∇[J^i(+μ)] _ θE_ v[ J_i( θ+μ v)] = = [∇J^i(+μ)] _ v[ _ θ J_i( θ+μ v)] = = [1μJ^i(+μ)] _ v [ 1μ J_i( θ+μ v) v ] (79) = = [1μ(J^i(+μ)−J^i())], _ v [ 1μ ( J_i( θ+μ v)- J_i( θ) ) v ], (80) where (79) uses the Stein’s identity and (80) comes follows the fact that [J^i()]=dtotE_ v[ J_i( θ) v]=0_d_tot. (i) By applying the L-smooth of J^i() J_i( θ), we can derive |J^i(+μ)−J^i()−μ∇J^i()⊤|≤Lμ22⊤. | J_i( θ+μ v)- J_i( θ)-μ _ θ J_i( θ) v |≤ Lμ^22 v v. (81) By using the definition on J^iμ() J^μ_i( θ) in (18), we further have |J^iμ()−J^i()| | J^μ_i( θ)- J_i( θ)| = = |[J^i(+μ)]−J^i()| |E_ v[ J_i( θ+μ v)]- J_i( θ) | = = |[J^i(+μ)]−[J^i()]−[μ∇J^i()⊤]| |E_ v[ J_i( θ+μ v)]-E_ v[ J_i( θ)]-E_ v[μ _ θ J_i( θ) v] | (82) ≤ ≤ [|J^i(+μ)−J^i()−μ∇J^i()⊤|] _ v [ | J_i( θ+μ v)- J_i( θ)-μ _ θ J_i( θ) v | ] ≤ ≤ Lμ22[⊤] Lμ^22E_ v[ v v] (83) = = Lμ2dtot2, Lμ^2d_tot2, (84) where (82) uses the fact that [∇J^i()⊤]=0E_ v[ _ θ J_i( θ) v]=0, (83) can be obtained by (81), and (84) can be achieved by the fact that [⊤]=dtotE_ v[ v v]=d_tot. (i) Recalling the definition of J^iμ() J^μ_i( θ) in (18) again, we have ‖∇J^iμ()−∇J^i()‖ \| _ θ J^μ_i( θ)- _ θ J_i( θ)\| = = ‖[∇J^i(+μ)−∇J^i()]‖ \|E_ v[ _ θ J_i( θ+μ v)- _ θ J_i( θ)] \| ≤ ≤ [‖∇J^i(+μ)−∇J^i()‖] _ v [ \| _ θ J_i( θ+μ v)- _ θ J_i( θ) \| ] ≤ ≤ Lμ[‖] L _ v[\| v\|] (85) ≤ ≤ Lμdtot, Lμ d_tot, (86) where (85) uses the L-smoothness of J^i() J_i( θ) and (86) can be achieved by the fact that [‖]≤dtotE_ v[\| v\|]≤ d_tot. (iv) For ‖1μ(J^i(+μ)−J^i())‖2 \| 1μ ( J_i( θ+μ v)- J_i( θ) ) v \|^2, we have ‖1μ(J^i(+μ)−J^i())‖2 \| 1μ ( J_i( θ+μ v)- J_i( θ) ) v \|^2 = = 1μ2(J^i(+μ)−J^i())2‖2 1μ^2 ( J_i( θ+μ v)- J_i( θ) )^2\| v\|^2 ≤ ≤ 1μ2(μ‖∇J^i()‖‖+μ2L2‖2)2‖2 1μ^2 (μ\| _ θ J_i( θ)\|\| v\|+ μ^2L2\| v\|^2 )^2\| v\|^2 (87) ≤ ≤ 1μ2(2μ2‖∇J^i()‖2‖2+μ4L22‖4)‖2 1μ^2 (2μ^2\| _ θ J_i( θ)\|^2\| v\|^2+ μ^4L^22\| v\|^4 )\| v\|^2 (88) = = 2‖∇J^i()‖2‖4+μ2L22‖6, 2\| _ θ J_i( θ)\|^2\| v\|^4+ μ^2L^22\| v\|^6, (89) where (87) uses the property of L-smooth of J^i() J_i( θ) and (88) comes from the fact that (x+y)2≤2x2+2y2(x+y)^2≤ 2x^2+2y^2 for all x,y∈ℝx,y . Taking the expectation of both sides of (89), we have [‖1μ(J^i(+μ)−J^i())‖2] _ v [ \| 1μ ( J_i( θ+μ v)- J_i( θ) ) v \|^2 ] ≤ ≤ [2‖∇J^i()‖2‖4+μ2L22‖6] _ v [2\| _ θ J_i( θ)\|^2\| v\|^4+ μ^2L^22\| v\|^6 ] = = 2dtot(dtot+2)‖∇J^i()‖2+μ2L2dtot(dtot+2)(dtot+4)2, 2d_tot(d_tot\!+\!2)\| _ θ J_i( θ)\|^2\!+\! μ^2L^2d_tot(d_tot\!+\!2)(d_tot\!+\!4)2, (90) where the last inequality can be achieved by the fact that [‖4]=dtot(dtot+2)E_ v[\| v\|^4]=d_tot(d_tot+2) and [‖6]=dtot(dtot+2)(dtot+4)E_ v[\| v\|^6]=d_tot(d_tot+2)(d_tot+4). □ 7.6 Proof of Theorem 2 Proof. (i) Recalling the definition of BiastBias_t in (21), we directly have Biast≤∥∇J(t)∥[∇J(t)−^t|ℱt]∥. _t≤ \| _ θJ( θ_t) \| \|E [ _ θJ( θ_t)- g_t |F_t ] \|. (91) Since ∇J(t)=(∇θ1J(t)⊤,⋯,∇θNJ(t)⊤)⊤ _ θJ( θ_t)= ( _ _1J( θ_t) ,·s, _ _NJ( θ_t) ) and ^t=(g^1,t⊤,⋯,g^N,t⊤)⊤ g_t= ( g _1,t,·s, g _N,t ) , for any agent i∈i , we have ∥[∇θiJ(t)−g^i,t|ℱt]∥ \|E [ _ _iJ( θ_t)- g_i,t |F_t ] \| = = ∥[∇θiJ(t)−∇θiJ^i(t)+∇θiJ^i(t)−∇θiJ^iμ(t) \|E [ _ _iJ( θ_t)- _ _i J_i( θ_t)+ _ _i J_i( θ_t)- _ _i J^μ_i( θ_t) +∇θiJ^iμ(t)−g^i,t|ℱt]∥ + _ _i J^μ_i( θ_t)- g_i,t |F_t ] \| ≤ ≤ ‖∇θiJ(t)−∇θiJ^i(t)‖+‖∇θiJ^i(t)−∇θiJ^iμ(t)‖ \| _ _iJ( θ_t)- _ _i J_i( θ_t) \|+ \| _ _i J_i( θ_t)- _ _i J^μ_i( θ_t) \| +∥[∇θiJ^iμ(t)−g^i,t|ℱt]∥ + \|E [ _ _i J^μ_i( θ_t)- g_i,t |F_t ] \| ≤ ≤ BR((H+1)γH+2γκ+1)(1−γ)2+Lμdtot BR ((H+1)γ^H+2γ^κ+1 )(1-γ)^2+Lμ d_tot +∥[∇θiJ^iμ(t)−g^i,t|ℱt]∥, + \|E [ _ _i J^μ_i( θ_t)- g_i,t |F_t ] \|, (92) where the last inequality follows from Theorem 1 and (i) of Lemma 3. For the last term ∥[∇θiJ^iμ(t)−g^i,t|ℱt]∥ \|E [ _ _i J^μ_i( θ_t)- g_i,t |F_t ] \| in the right side of (92), we have ∥[∇θiJ^iμ(t)−g^i,t|ℱt]∥ \|E [ _ _i J^μ_i( θ_t)- g_i,t |F_t ] \| = = ∥[1μ(J^i(t+μt)−J^i(t))vi,t|ℱt] \|E [ 1μ ( J_i( θ_t+μ v_t)- J_i( θ_t) )v_i,t |F_t ] −[1Kμ∑k=1Kσ−1(p^it,k)vi,t|ℱt]∥, -E [ 1Kμ _k=1^Kσ^-1( p^t,k_i)v_i,t |F_t ] \|, (93) which use the definition of g^i,t g_i,t in (11) and (i) of Lemma 3. Since each trajectory pair (τiκ,0t,k,τiκ,1t,k)(τ^t,k_N^κ_i,0,τ^t,k_N^κ_i,1) is generated independently from other trajectory pairs, we have [1Kμ∑k=1Kσ−1(p^it,k)vi,t|ℱt] [ 1Kμ _k=1^Kσ^-1( p^t,k_i)v_i,t |F_t ] = = [[1Kμ∑k=1Kσ−1(p^it,k)|vi,t]vi,t|ℱt] [E [ 1Kμ _k=1^Kσ^-1( p^t,k_i) |v_i,t ]v_i,t |F_t ] (94) = = 1μ[[σ−1(p^it,k)|vi,t]vi,t|ℱt] 1μE [E [σ^-1( p^t,k_i) |v_i,t ]v_i,t |F_t ] (95) = = 1μ[[r^i(τiκ,1t,k)−r^i(τiκ,0t,k)|vi,t]vi,t|ℱt] 1μE [E [ r_i(τ^t,k_N^κ_i,1)- r_i(τ^t,k_N^κ_i,0) |v_i,t ]v_i,t |F_t ] +1μ[[(σ−1(p^it,k)−(r^i(τiκ,1t,k)−r^i(τiκ,0t,k)))|vi,t] + 1μE [E [ (σ^-1( p^t,k_i)-( r_i(τ^t,k_N^κ_i,1)- r_i(τ^t,k_N^κ_i,0)) ) |v_i,t ] ×vi,t|ℱt], × v_i,t |F_t ], (96) where (94) uses the law of total expectation and (95) uses the fact that the trajectory pairs are generated by the same policy pair and mutually independent. Substituting (96) into (93), we have ∥[∇θiJ^iμ(t)−g^i,t|ℱt]∥ \|E [ _ _i J^μ_i( θ_t)- g_i,t |F_t ] \| ≤ ≤ ∥1μ[[(J^i(t+μt)−J^i(t)−r^i(τiκ,1t,k) \| 1μE [E [ ( J_i( θ_t+μ v_t)- J_i( θ_t)- r_i(τ^t,k_N^κ_i,1) +r^i(τiκ,0t,k))|vi,t]vi,t|ℱt]−1μ[[(σ−1(p^it,k) + r_i(τ^t,k_N^κ_i,0) ) |v_i,t ]v_i,t |F_t ]- 1μE [E [ (σ^-1( p^t,k_i) −(r^i(τiκ,1t,k)−r^i(τiκ,0t,k)))|vi,t]vi,t|ℱt]∥ -( r_i(τ^t,k_N^κ_i,1)- r_i(τ^t,k_N^κ_i,0)) ) |v_i,t ]v_i,t |F_t ] \| (97) ≤ ≤ dtotμ(Lσ2logM+4R(1−γH)(1−γ)M2) d_totμ (L_σ 2 MM+ 4R(1-γ^H)(1-γ)M^2 ) ≤ ≤ 2Lσdtotμ2logM, 2L_σ d_totμ 2 MM, (98) where the second inequality follows from the facts that [J^i(t+μt)−r^i(τiκ,1t,k)]=[J^i(t)−r^i(τiκ,0t,k)]=0E [ J_i( θ_t+μ v_t)- r_i(τ^t,k_N^κ_i,1) ]=E [ J_i( θ_t)- r_i(τ^t,k_N^κ_i,0) ]=0, the norm bound [‖vi,t‖]≤dtotE[\|v_i,t\|]≤ d_tot, and the estimation error result in (2), and the last inequality follows from the selected M≥maxe,2(R2(1−γH)2(1−γ)2Lσ2)13M≥ \e,2( R^2(1-γ^H)^2(1-γ)^2L^2_σ) 13\. By substituting (98) into (92) and combining it with (91), we can finish the proof of part (i) of Theorem 2. (i) By the definition of g^i,t g_i,t in (11), we define Vari,t=[‖g^i,t‖2|ℱt] _i,t=E[\| g_i,t\|^2|F_t] (99) and have Vart=∑i=1NVari,tVar_t= _i=1^NVar_i,t. Define Vari,t(1)Var^(1)_i,t, Vari,t(2)Var^(2)_i,t, and Vari,t(3)Var^(3)_i,t as follows: Vari,t(1)=[∥1Kμ∑k=1K(σ−1(p^it,k)−(r^i(τiκ,1t,k)−r^i(τiκ,0t,k)))vi,t∥2|ℱt]Vari,t(2)=[∥1μ(1K∑k=1K(r^i(τiκ,1t,k)−r^i(τiκ,0t,k))−(J^i(t+μt)−J^i(t)))vi,t∥2|ℱt]Vari,t(3)=[‖1μ(J^i(t+μt)−J^i(t))vi,t‖2|ℱt]. \ array[]l\!Var^(1)_i,t\!=\!E [ \| 1Kμ _k=1^K (σ^-1( p^t,k_i)- ( r_i(τ^t,k_N^κ_i,1)\\ \;\;\;\;\;\;\;\;\;\;\;\;- r_i(τ^t,k_N^κ_i,0) ) )v_i,t \|^2 |F_t ]\\ \!Var^(2)_i,t\!=\!E [ \| 1μ ( 1K _k=1^K ( r_i(τ^t,k_N^κ_i,1)- r_i(τ^t,k_N^κ_i,0) )\\ \;\;\;\;\;\;\;\;\;\;\;\;- ( J_i( θ_t+μ v_t)- J_i( θ_t) ) )v_i,t \|^2 |F_t ]\\ \!Var^(3)_i,t\!=\!E [ \| 1μ ( J_i( θ_t+μ v_t)- J_i( θ_t) )v_i,t \|^2 |F_t ]. array . (105) For Vari,tVar_i,t in (99), we have Vari,t= _i,t= [‖1Kμ∑k=1Kσ−1(p^it,k)vi,t‖2|ℱt] [ \| 1Kμ _k=1^Kσ^-1( p^t,k_i)v_i,t \|^2 |F_t ] ≤ ≤ 3(Vari,t(1)+Vari,t(2)+Vari,t(3)), 3 (Var^(1)_i,t+Var^(2)_i,t+Var^(3)_i,t ), (106) where the inequality can be obtained by the fact that (a+b+c)2≤3(a2+b2+c2)(a+b+c)^2≤ 3(a^2+b^2+c^2) for all a,b,c∈ℝa,b,c . For the first term, Vari,t(1)Var^(1)_i,t, which arises from the estimation error in human preferences, we have Vari,t(1)= ^(1)_i,t= 1K2μ2[|∑k=1K(σ−1(p^it,k)−(r^i(τiκ,1t,k) 1K^2μ^2E [ | _k=1^K (σ^-1( p^t,k_i)- ( r_i(τ^t,k_N^κ_i,1) −r^i(τiκ,0t,k)))|2×∥vi,t∥2|ℱt] - r_i(τ^t,k_N^κ_i,0) ) ) |^2×\|v_i,t\|^2 |F_t ] ≤ ≤ 1K2μ2[|∑k=1K(σ−1(p^it,k)−(r^i(τiκ,1t,k) 1K^2μ^2E [ | _k=1^K (σ^-1( p^t,k_i)- ( r_i(τ^t,k_N^κ_i,1) −r^i(τiκ,0t,k)))|4|ℱt]12×[∥vi,t∥4|ℱt]12 - r_i(τ^t,k_N^κ_i,0) ) ) |^4 |F_t ] 12×E [\|v_i,t\|^4 |F_t ] 12 (107) ≤ ≤ di(di+2)K2μ2[K3∑k=1K|σ−1(p^it,k)−(r^i(τiκ,1t,k) d_i(d_i+2)K^2μ^2E [K^3 _k=1^K |σ^-1( p^t,k_i)- ( r_i(τ^t,k_N^κ_i,1) −r^i(τiκ,0t,k))|4|ℱt]12 - r_i(τ^t,k_N^κ_i,0) ) |^4 |F_t ] 12 (108) ≤ ≤ di(di+2)μ2(4Lσ4(logM)2M2 d_i(d_i+2)μ^2 ( 4L^4_σ( M)^2M^2 +256R4(1−γH)4(1−γ)4M2)12 + 256R^4(1-γ^H)^4(1-γ)^4M^2 ) 12 (109) ≤ ≤ 22di(di+2)Lσ2logMμ2M, 2 2d_i(d_i+2)L^2_σ Mμ^2M, (110) where (107) uses the Cauchy-Schwarz inequality, (108) uses the facts that [‖vi,t‖4]=di(di+2)E[\|v_i,t\|^4]=d_i(d_i+2) and (∑k=1Kxk)4≤K3∑k=1Kxk4 ( _k=1^Kx_k )^4≤ K^3 _k=1^Kx_k^4 for all xk∈ℝx_k , (109) follows from (2), and the last inequality achieves by the choosing M≥exp(8R2(1−γH)2(1−γ)2Lσ2)M≥ ( 8R^2(1-γ^H)^2(1-γ)^2L^2_σ ). For the second term, Vari,t(2)Var^(2)_i,t, which comes from using the empirical rewards of agent i’s κ-hop neighbors to the truncated objective J^i() J_i( θ) in (4.1), we have Vari,t(2)= ^(2)_i,t= 1μ2K2[|∑k=1K((r^i(τiκ,1t,k)−r^i(τiκ,0t,k)) 1μ^2K^2E [ | _k=1^K ( ( r_i(τ^t,k_N^κ_i,1)- r_i(τ^t,k_N^κ_i,0) ) −(J^i(t+μt)−J^i(t)))|2∥vi,t∥2|ℱt] - ( J_i( θ_t+μ v_t)- J_i( θ_t) ) ) |^2\|v_i,t\|^2 |F_t ] ≤ ≤ di(di+2)μ2K2[|∑k=1K((r^i(τiκ,1t,k)−r^i(τiκ,0t,k)) d_i(d_i+2)μ^2K^2E [ | _k=1^K ( ( r_i(τ^t,k_N^κ_i,1)- r_i(τ^t,k_N^κ_i,0) ) −(J^i(t+μt)−J^i(t)))|4|ℱt]12, - ( J_i( θ_t+μ v_t)- J_i( θ_t) ) ) |^4 |F_t ] 12, (111) where the inequality follows from the Cauchy-Schwarz inequality and the fact that [‖vi,t‖4]=di(di+2)E[\|v_i,t\|^4]=d_i(d_i+2). Let ξit,k=(r^i(τiκ,1t,k)−r^i(τiκ,0t,k))−(J^i(t+μt)−J^i(t)) _i^t,k= ( r_i(τ^t,k_N^κ_i,1)- r_i(τ^t,k_N^κ_i,0) )- ( J_i( θ_t+μ v_t)- J_i( θ_t) ), (111) can be further written as Vari,t(2)≤ ^(2)_i,t≤ di(di+2)μ2K2[(∑k=1Kξit,k)4|ℱt]12. d_i(d_i+2)μ^2K^2E [ ( _k=1^K _i^t,k )^4 |F_t ] 12. (112) Recalling the definitions of (7) and (4.1), we have that [ξit,k]=0E[ _i^t,k]=0, |ξit,k|≤4R(1−γH)1−γ| _i^t,k|≤ 4R(1-γ^H)1-γ, and var(ξit,k)≤16R2(1−γH)2(1−γ)2var( _i^t,k)≤ 16R^2(1-γ^H)^2(1-γ)^2. By using Lemma 4, we can get [(∑k=1Kξit,k)4|ℱt]12≤ [ ( _k=1^K _i^t,k )^4 |F_t ] 12≤ 163KR2(1−γH)2(1−γ)2 16 3KR^2(1-γ^H)^2(1-γ)^2 +16KR2(1−γH)2(1−γ)2 + 16 KR^2(1-γ^H)^2(1-γ)^2 ≤ ≤ 44KR2(1−γ)2, 44KR^2(1-γ)^2, (113) where the last inequality follows from K≥1K≥ 1 and 0<γ<10<γ<1. Substituting (7.6) into (112), we can have Vari,t(2)≤ ^(2)_i,t≤ 44di(di+2)R2μ2(1−γ)2K. 44 d_i(d_i+2)R^2μ^2(1-γ)^2K. (114) For the last term, Vari,t(3)Var^(3)_i,t, we use (iv) of Lemma 3 and can get Vari,t(3)≤ ^(3)_i,t≤ 2dtot(dtot+2)∥∇J^i(t)−∇θiJ(t) 2d_tot(d_tot+2)\| _ θ J_i( θ_t)- _ _iJ( θ_t) +∇θiJ(t)∥2+μ2L2dtot(dtot+2)(dtot+4)2 + _ _iJ( θ_t)\|^2+ μ^2L^2d_tot(d_tot+2)(d_tot+4)2 ≤ ≤ 4dtot(dtot+2)‖∇θiJ(t)‖2 4d_tot(d_tot+2)\| _ _iJ( θ_t)\|^2 +4B2R2((H+1)γH+2γκ+1)2dtot(dtot+2)(1−γ)4 + 4B^2R^2 ((H+1)γ^H+2γ^κ+1 )^2d_tot(d_tot+2)(1-γ)^4 +μ2L2dtot(dtot+2)(dtot+4)2, + μ^2L^2d_tot(d_tot+2)(d_tot+4)2, (115) where the inequality can be achieved by Theorem 1. By substituting (110), (114), and (115) into (7.6), and utilizing the relation Vart=∑i=1NVari,tVar_t= _i=1^NVar_i,t, the proof of Part (i) is thus completed. □ 7.7 Proof of Theorem 3 Proof. By the property of L-Lipschitz continuous of ∇J() _ θJ( θ) in Assumption 6, we have J(t)−J(t+1) J( θ_t)-J( θ_t+1) ≤ ≤ ⟨−∇J(t),t+1−t⟩+L2‖t+1−t‖2 - _ θJ( θ_t), θ_t+1- θ_t + L2\| θ_t+1- θ_t\|^2 = = −α⟨∇J(t),^t⟩+Lα22‖^t‖2 -α _ θJ( θ_t), g_t + Lα^22\| g_t\|^2 (116) = = −α‖∇J(t)‖2+α⟨∇J(t),∇J(t)−^t⟩ -α\| _ θJ( θ_t)\|^2+α _ θJ( θ_t), _ θJ( θ_t)- g_t +Lα22‖^t‖2, + Lα^22\| g_t\|^2, (117) where (116) follows from (12). We take a conditional expectation of both sides of (117) over the σ-algebra ℱtF_t of iteration t and obtain [J(t)−J(t+1)|ℱt] [J( θ_t)-J( θ_t+1)|F_t] ≤ ≤ −α‖∇J(t)‖2+αBiast+Lα22Vart -α\| _ θJ( θ_t)\|^2+ _t+ Lα^22Var_t ≤ ≤ −α∥∇J(t)∥2+α∥∇J(t)∥(Biast(i)+Biast(i) -α\| _ θJ( θ_t)\|^2+α \| _ θJ( θ_t) \| (Bias^(i)_t+Bias^(i)_t +Biast(i))+Lα22(12Ndtot(dtot+2)∥∇J(t)∥2 +Bias^(i)_t )+ Lα^22 (12Nd_tot(d_tot+2)\| _ θJ( θ_t)\|^2 +Vart(i)+Vart(i)+Vart(iv)+Vart(v)), +Var^(i)_t+Var^(i)_t+Var^(iv)_t+Var^(v)_t ), (118) where the last inequality can be obtained by Theorem 2. Since α=112LNdtot(dtot+2)α= 112LNd_tot(d_tot+2), we can further simplify (118) as [J(t)−J(t+1)|ℱt] [J( θ_t)-J( θ_t+1)|F_t] ≤ ≤ −α2∥∇J(t)∥2+α∥∇J(t)∥(Biast(i)+Biast(i) - α2\| _ θJ( θ_t)\|^2+α \| _ θJ( θ_t) \| (Bias^(i)_t+Bias^(i)_t +Biast(i))+Lα22(Vart(i)+Vart(i)+Vart(iv) +Bias^(i)_t )+ Lα^22 (Var^(i)_t+Var^(i)_t+Var^(iv)_t +Vart(v)). +Var^(v)_t ). (119) Next, we will consider two different cases. 1) When ‖∇J(t)‖\| _ θJ( θ_t)\| is large and satisfies ‖∇J(t)‖≥4(Biast(i)+Biast(i)+Biast(i))\| _ θJ( θ_t)\|≥ 4 (Bias^(i)_t+Bias^(i)_t+Bias^(i)_t ), (119) can be rewritten as [J(t)−J(t+1)|ℱt] [J( θ_t)-J( θ_t+1)|F_t] ≤ ≤ −α4∥∇J(t)∥2+Lα22(Vart(i)+Vart(i)+Vart(iv) - α4\| _ θJ( θ_t)\|^2+ Lα^22 (Var^(i)_t+Var^(i)_t+Var^(iv)_t +Vart(v)). +Var^(v)_t ). (120) 2) On the other hand, the policy gradient ‖∇J(t)‖≤4(Biast(i)+Biast(i)+Biast(i))\| _ θJ( θ_t)\|≤ 4 (Bias^(i)_t+Bias^(i)_t+Bias^(i)_t ), (119) can further write as [J(t)−J(t+1)|ℱt] [J( θ_t)-J( θ_t+1)|F_t] ≤ ≤ −α2‖∇J(t)‖2+4α(Biast(i)+Biast(i)+Biast(i))2 - α2\| _ θJ( θ_t)\|^2+4α (Bias^(i)_t+Bias^(i)_t+Bias^(i)_t )^2 +Lα22(Vart(i)+Vart(i)+Vart(iv)+Vart(v)). + Lα^22 (Var^(i)_t+Var^(i)_t+Var^(iv)_t+Var^(v)_t ). (121) By taking the maximum of both bounds given in (120) and (121) and subsequently computing the expectation, we obtain [J(t)−J(t+1)] [J( θ_t)-J( θ_t+1)] ≤ ≤ −α4[‖∇J(t)‖2]+4α(Biast(i)+Biast(i)+Biast(i))2 - α4E[\| _ θJ( θ_t)\|^2]+4α (Bias^(i)_t+Bias^(i)_t+Bias^(i)_t )^2 +Lα22(Vart(i)+Vart(i)+Vart(iv)+Vart(v)) + Lα^22 (Var^(i)_t+Var^(i)_t+Var^(iv)_t+Var^(v)_t ) ≤ ≤ −α4[‖∇J(t)‖2] - α4E[\| _ θJ( θ_t)\|^2] +13αB2R2N((H+1)γH+2γκ+1)2(1−γ)4 + 13α B^2R^2N ((H+1)γ^H+2γ^κ+1 )^2(1-γ)^4 +(12αL2Ndtot+αL2(dtot+4)16)μ2 + (12α L^2Nd_tot+ α L^2(d_tot+4)16 )μ^2 +(6αR2(1−γ)2K+96αLσ2NdtotlogM+αLσ2logM4M)1μ2 \!+\! ( 6α R^2(1-γ)^2K\!+\! 96α L^2_σNd_tot MM\!+\! α L^2_σ M4M ) 1μ^2 (122) ≤ ≤ −α4[‖∇J(t)‖2] - α4E[\| _ θJ( θ_t)\|^2] +13αB2R2N((H+1)γH+2γκ+1)2(1−γ)4+13αL2Ndtotμ2 \!+\! 13α B^2R^2N ((H\!+\!1)γ^H\!+\!2γ^κ\!+\!1 )^2(1\!-\!γ)^4\!+\!13α L^2Nd_totμ^2 +(6αR2(1−γ)2K+97αLσ2NdtotlogM)1μ2, + ( 6α R^2(1-γ)^2K+ 97α L^2_σNd_tot MM ) 1μ^2, (123) where (122) follows from Theorem 2 and (123) comes from dtot≥1d_tot≥ 1. Since μ2=maxR(1−γ)LKNdtot,3LσLlogMμ^2= \ R(1-γ)L KNd_tot, 3L_σL MM \, we have 13αL2Ndtotμ2≥6αR2K(1−γ)2μ213α L^2Nd_totμ^2≥ 6α R^2K(1-γ)^2μ^2 and 13αL2Ndtotμ2≥97αLσ2NdtotlogMμ213α L^2Nd_totμ^2≥ 97α L^2_σNd_tot MMμ^2. By using these facts, (123) can further simplified to [J(t)−J(t+1)] [J( θ_t)-J( θ_t+1)] ≤ ≤ −α4[‖∇J(t)‖2] - α4E[\| _ θJ( θ_t)\|^2] +13αB2R2N((H+1)γH+2γκ+1)2(1−γ)4+39αL2Ndtotμ2. +\! 13α B^2R^2N ((H\!+\!1)γ^H\!+\!2γ^κ\!+\!1 )^2(1\!-\!γ)^4\!+\!39α L^2Nd_totμ^2. (124) By performing a telescoping summation for (124) and rearranging the terms, we obtain the following result: 1T∑t=0T−1[‖∇J(t)‖2] 1T _t=0^T-1E[\| _ θJ( θ_t)\|^2] ≤ ≤ 4([J(0)]−[J(T)])Tα 4 (E[J( θ_0)]-E[J( θ_T)] )Tα +52B2R2N((H+1)γH+2γκ+1)2(1−γ)4+156L2Ndtotμ2 + 52B^2R^2N ((H+1)γ^H+2γ^κ+1 )^2(1-γ)^4+156L^2Nd_totμ^2 = = 96LNRdtot(dtot+2)(1−γ)T 96LNRd_tot(d_tot+2)(1-γ)T +52B2R2N((H+1)γH+2γκ+1)2(1−γ)4+156L2Ndtotμ2 + 52B^2R^2N ((H+1)γ^H+2γ^κ+1 )^2(1-γ)^4+156L^2Nd_totμ^2 = = (LNRdtot(dtot+2)(1−γ)T ( LNRd_tot(d_tot+2)(1-γ)T +B2R2N((H+1)γH+2γκ+1)2(1−γ)4 + B^2R^2N ((H+1)γ^H+2γ^κ+1 )^2(1-γ)^4 +maxLRNdtot(1−γ)K,LNdtotLσlogM), + \ LR Nd_tot(1-γ) K,LNd_totL_σ MM \ ), where the first inequality can be obtained by −R1−γ≤J()≤R1−γ -R1-γ≤ J( θ)≤ R1-γ and α=112LNdtot(dtot+2)α= 112LNd_tot(d_tot+2), and the last equality uses μ2=maxR(1−γ)LKNdtot,3LσLlogMμ^2= \ R(1-γ)L KNd_tot, 3L_σL MM \. □