Paper deep dive
Scalable Policy Optimization for Networked Multi-Agent Reinforcement Learning with Continuous State-Action Spaces
Dongming Wang, Pengcheng Dai, Wenwu Yu, Wei Ren
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 7/22/2026, 2:06:43 AM
Summary
The paper introduces the Continuous Distributed Coupled Policy Gradient (CDCPG) algorithm for cooperative reinforcement learning in networked Markov decision processes with continuous state and action spaces. It addresses scalability by using localized actors and critics based on spectral random-feature representations. Key contributions include a localized Bellman theory, a proof of dimensional obstruction for temporal-difference stability, sample complexity guarantees of O~(epsilon^-2), and an adaptive-locality rule for selecting neighborhood radius.
Entities (8)
Relation Signals (7)
Wei Ren → affiliatedwith → University of California, Riverside
confidence 95% · D. Wang and W. Ren are with the Department of Electrical and Computer Engineering, University of California, Riverside
Dongming Wang → affiliatedwith → University of California, Riverside
confidence 95% · D. Wang and W. Ren are with the Department of Electrical and Computer Engineering, University of California, Riverside
CDCPG → solves → Networked Markov Decision Process
confidence 95% · We develop the Continuous Distributed Coupled Policy Gradient (CDCPG) algorithm for cooperative reinforcement learning in networked Markov decision processes
CDCPG → guarantees → O~(epsilon^-2) sample complexity
confidence 92% · CDCPG drives an averaged per-agent stationarity measure to within any excess epsilon of an explicitly characterized approximation floor using O~(epsilon^-2) shared-oracle samples
CDCPG → uses → Least-Squares Temporal-Difference
confidence 90% · localized least-squares temporal-difference critic evaluates a truncated action-value function
CDCPG → uses → Random Fourier Features
confidence 90% · spectral random-feature representation of the local transition kernel
CDCPG → relieson → Exponential Spatial Decay
confidence 88% · under exponential spatial decay of agent interactions... CDCPG drives an averaged per-agent stationarity measure
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We develop the Continuous Distributed Coupled Policy Gradient (CDCPG) algorithm for cooperative reinforcement learning in networked Markov decision processes with continuous state and action spaces. Each agent maintains a local actor over a bounded graph neighborhood, and a localized least-squares temporal-difference critic evaluates a truncated action-value function through a spectral random-feature representation of the local transition kernel. The analysis makes four contributions. First, the truncated action-value function is constructed as a conditional expectation over the neighborhood, yielding a well-posed localized Bellman theory that removes the continuation-kernel mismatch of naive truncation arguments. Second, we expose a dimensional obstruction to temporal-difference stability for normalized random features and prove an unconditional excitation bound that reduces stability to a symmetric persistence-of-excitation condition, monitorable through an online matrix-concentration certificate. Third, under exponential spatial decay of agent interactions, the excitation condition, and smoothness of the objective, CDCPG drives an averaged per-agent stationarity measure to within any excess $\epsilon$ of an explicitly characterized approximation floor using $\widetilde{\mathcal{O}}(\epsilon^{-2})$ shared-oracle samples, and the excess dependence matches the smooth nonconvex first-order rate; per-agent computation and communication are governed by the neighborhood size rather than the network size. Fourth, an adaptive-locality rule selects the radius that balances truncation and graph-decay residuals against the target accuracy. Experiments on a networked linear-quadratic benchmark corroborate the locality and feature-dimension predictions.
Tags
Links
- Source: https://arxiv.org/abs/2607.18554v1
- Canonical: https://arxiv.org/abs/2607.18554v1
Trouble viewing inline? Open PDF directly →
Full Text
267,135 characters extracted from source content.
Expand or collapse full text
Scalable Policy Optimization for Networked Multi-Agent Reinforcement Learning with Continuous State-Action Spaces Dongming Wang, Pengcheng Dai, Wenwu Yu, , Wei Ren D. Wang and W. Ren are with the Department of Electrical and Computer Engineering, University of California, Riverside, CA 92521, USA. wdong025, wei.ren@ucr.edu.P. Dai is with the Engineering Systems and Design Pillar, Singapore University of Technology and Design, Singapore 487372. Jldaipc@163.com.W. Yu is with the Frontiers Science Center for Mobile Information Communication and Security, School of Mathematics, Southeast University, Nanjing 211102, China, and also with Purple Mountain Laboratories, Nanjing, 211102, China. wwyu@seu.edu.cn. Abstract We develop the Continuous Distributed Coupled Policy Gradient (CDCPG) algorithm for cooperative reinforcement learning in networked Markov decision processes with continuous state and action spaces. Each agent maintains a local actor over a bounded graph neighborhood, and a localized least-squares temporal-difference critic evaluates a truncated action-value function through a spectral random-feature representation of the local transition kernel. The analysis makes four contributions. First, the truncated action-value function is constructed as a conditional expectation over the neighborhood, yielding a well-posed localized Bellman theory that removes the continuation-kernel mismatch of naive truncation arguments. Second, we expose a dimensional obstruction to temporal-difference stability for normalized random features and prove an unconditional excitation bound that reduces stability to a symmetric persistence-of-excitation condition, monitorable through an online matrix-concentration certificate. Third, under exponential spatial decay of agent interactions, the excitation condition, and smoothness of the objective, CDCPG drives an averaged per-agent stationarity measure to within any excess ϵε of an explicitly characterized approximation floor using ~(ϵ−2) O(ε^-2) shared-oracle samples, and the excess dependence matches the smooth nonconvex first-order rate; per-agent computation and communication are governed by the neighborhood size rather than the network size. Fourth, an adaptive-locality rule selects the radius that balances truncation and graph-decay residuals against the target accuracy. Experiments on a networked linear-quadratic benchmark corroborate the locality and feature-dimension predictions. I Introduction Multi-agent reinforcement learning (MARL) in networked systems is a foundational paradigm for distributed decision-making across modern cyber-physical systems [32, 10, 22]. The defining feature of such systems is that each agent’s dynamics, rewards, and observations are influenced by nearby neighbors rather than uniformly by all agents. The central challenge is scalability: the joint state-action space grows exponentially with the number of agents n, rendering centralized methods intractable, while purely decentralized methods often fail to coordinate. Localized methods that exploit spatial structure occupy the principled middle ground [22, 23, 17]. I-A Related Work Networked multi-agent reinforcement learning and exponential decay. The foundational scalability result for networked Markov decision processes (MDPs) is due to Qu et al. [22, 23], who introduced the exponential decay property: under spatial coupling, each agent’s value function depends weakly on the states and actions of distant neighbors, with the influence decaying geometrically in graph distance. This property justifies truncated local approximations with quantifiable bias and underlies the polynomial-in-network-size sample complexity of subsequent scalable methods. Lin et al. [17] extended the analysis to stochastic settings with explicit finite-sample guarantees under a generative model, and related work has established global-convergence guarantees for localized policy iteration [34]. Earlier work on fully decentralized actor-critic methods [33, 8] provided consensus-based algorithms whose analyses rely on asymptotic mixing rather than explicit spatial decay; subsequent extensions [16, 7] study finite-sample behavior under various communication protocols. The cited works address discrete state-action spaces; extending the decay-driven framework to continuous domains is non-trivial because truncation now interacts with kernel-approximation error, and the policy-evaluation step itself requires function approximation with a well-conditioned design matrix. Continuous-domain reinforcement learning via spectral methods. For continuous state-action spaces, function approximation is unavoidable, and spectral methods provide a natural approach with explicit approximation guarantees. Random Fourier Features (RFF) [24, 18] approximate translation-invariant kernels by finite-dimensional inner products of trigonometric functions, with high-probability uniform-approximation guarantees on compact sets. This makes them well suited to kernel-ridge policy evaluation and to settings where the kernel itself is induced by the dynamics rather than chosen for representational convenience. Ren et al. [26] combined spectral dynamic embeddings with the networked-MDP framework and showed that the per-agent accuracy rate matches the discrete case under a generative model with shared trajectories. Their analysis, however, postulates a bounded inverse ‖i−1‖≤D M_i^-1 ≤ D for the least-squares temporal-difference (LSTD) design matrix as a problem primitive, without linking D to the random-feature dimension m, to the policy parameter θ, or to any quantity that can be monitored from samples. Our temporal-difference (TD) stability hypothesis is designed to make this dependence explicit: the stability constant is treated as a feature-dimension-dependent primitive μM(m) _M(m) with a provable obstruction to dimension-free constants in Proposition 2, accompanied by a matrix-Bernstein diagnostic whose false-certification probability is at most δ for the population TD-stability component along realized iterates in Proposition 3. The random-feature residual is then accounted for as a structural-floor component rather than as an accuracy-tunable quantity. LSTD learning and matrix concentration. The LSTD framework introduced by Bradtke and Barto [6] and refined by Boyan [5] provides a natural batch method for policy evaluation under linear function approximation; its finite-sample analysis was developed by Lazaric et al. [15]. The related TD(0) iteration was analyzed in finite samples by Bhandari et al. [4], who established explicit rates under linear function approximation and identified the role of the smallest eigenvalue of the feature covariance. The technical toolkit for the matrix-concentration arguments in our paper comes from Tropp’s matrix-Bernstein inequalities [29], Vershynin’s high-dimensional probability framework [30], and Pinelis’s dimension-free Hoeffding-type inequality for Hilbert-space martingales [21, Thm. 3.5]. Persistence-of-excitation results from adaptive control [20] provide a structural complement: they identify conditions under which the smallest singular value of a regressor design matrix is uniformly bounded below along realized trajectories, which motivates the trajectory-conditional formulation of our TD-stability hypothesis. Policy-gradient sample complexity and lower bounds. The policy-gradient theorem of Sutton et al. [28] is the conceptual basis for our update rule. For finite-sample analysis, the most directly relevant benchmark is the smooth nonconvex stochastic lower bound of Arjevani et al. [2], namely Ω(ϵg−4) ( _g^-4) oracle calls to drive ‖∇F‖≤ϵg ∇ F ≤ _g, i.e. Ω(ϵ−2) (ε^-2) under the squared-stationarity convention ϵ=ϵg2ε= _g^2 used here; Agarwal et al. [1] provide a complementary theoretical framework specific to policy-gradient methods, characterizing global convergence under softmax and other parameterizations. In the distributed setting, decentralized actor-critic algorithms have been analyzed by Zhang et al. [33], Doan et al. [8], Lin et al. [16], and Chu et al. [7], typically under consensus-based parameter sharing rather than the spatial-locality model considered here. The averaged-per-agent stationarity measure we adopt is, in spirit, the per-agent-normalized convention used in the distributed-MARL literature [22, 17, 26]; it removes the network-size factor that the unnormalized aggregate-objective measure would otherwise carry and preserves the canonical lower-bound rate at the per-agent level. Empirical multi-agent reinforcement learning and attention-based methods. A parallel line of work has produced influential empirical algorithms for cooperative and competitive multi-agent settings. Lowe et al. [19] introduced the multi-agent deep deterministic policy gradient (MADDPG) framework with centralized training and decentralized execution; Foerster et al. [11] proposed the counterfactual multi-agent policy gradient (COMA) with a centralized critic that uses counterfactual baselines for credit assignment; Iqbal and Sha [14] introduced attention-based actor-critic for selective neighbor querying; and Yu et al. [31] demonstrated that suitably configured multi-agent proximal policy optimization (MAPPO) is competitive across standard benchmarks. These methods scale by architectural design rather than by exploiting graph-locality, and their finite-sample analyses remain open in general. Our work is complementary: we provide finite-sample guarantees with explicit error decompositions by working in a more structured (but still continuous) setting where exponential decay is available as a hypothesis. Networked control applications. The motivation for scalable continuous-state networked reinforcement learning comes largely from cyber-physical systems. Shin et al. [27] apply localized policy-gradient methods to power-system frequency control, demonstrating that locality-aware methods achieve near-optimal control with substantially reduced communication. Feng [10] develops stability-aware multi-agent learning for networked control. Classical results on radial distribution network reconfiguration [3] and modern reviews [32] together identify a recurring application profile: continuous-valued states and actions, sparse coupling, hard requirements on monitorable conditioning constants, since deployment teams need diagnostics observable from realized trajectories, and tolerance for approximation and localization floors, which finite-compute deployments commonly exhibit. These features motivate every design choice in CDCPG: the trajectory-conditional TD-stability hypothesis with a sample-level diagnostic, the fixed-dimension random-feature treatment with explicit floor accounting, the conditional-expectation truncation that produces a well-defined Bellman residual, and the averaged-per-agent stationarity measure that scales properly with network size. I-B Contributions This work refines spectral localized policy-gradient analysis for continuous networked MDPs in four directions. Technical challenges. Four difficulties separate the continuous networked setting from its tabular counterpart and shape the entire analysis. (C1) Loss of tabular localization. The exponential-decay mechanism that justifies truncated critics in finite-state models must be re-derived at the level of conditional expectations of QiπQ_i^π over local state–action windows, and the truncation must commute with a Bellman fixed point that is well defined only up to null sets of the occupancy measure (Section IV). (C2) Dimension-limited conditioning. The population TD design matrix admits no dimension-free lower singular-value bound (Proposition 2), so stability must be formulated as a feature-dimension-aware primitive and, where possible, reduced to a feature-excitation premise (Lemma 3). (C3) Signed global function approximation. Random-feature approximants of transition densities are signed and unnormalized, so uniform compact-core kernel bounds must be converted into global ℒ1L^1 control with explicit envelopes and an explicit dimensional constant (Theorem 1). (C4) Localized credit assignment with provable bias. Distributed gradient estimators aggregate neighboring critics whose statistical errors, within-bin fluctuations, and truncation residuals enter a four-component structural floor that the nonconvex optimization analysis must carry explicitly; see Sections V–VI. Each contribution below addresses one of (C1)–(C4). 1. Conditional-expectation truncation. We define the truncated action-value function as a conditional expectation over the local neighborhood under the discounted occupancy, with an auxiliary local Bellman operator whose fixed-point residual is bounded explicitly in Section IV. This makes the truncation error a clean structural quantity rather than an artifact of an ill-posed local fixed point. 2. Feature-dimension-aware TD stability. We make the bounded-inverse postulate of prior spectral methods [26] explicit and dimension-aware, restating it as the feature-dimension-dependent temporal-difference stability hypothesis of Assumption 4, and prove in Proposition 2 a dimensional obstruction showing that dimension-free stability constants are impossible, so that the analysis operates in the fixed-m regime with the random-feature dimension treated as a problem primitive. Lemma 3 establishes the unconditional excitation bound σmin(i)≥(1−γ)λmin(i) _ (M_i θ)≥(1- γ) _ (H_i θ) under occupancy sampling, reducing the hypothesis to a symmetric feature-excitation condition. A strictly weaker trajectory-conditional version (Assumption 5) is paired with a matrix-Bernstein diagnostic of controlled false-certification rate (Proposition 3). Both (C) and (C′) are unverified structural premises: the excitation lemma is a reduction, not a verification, and the probability 1−δM(m)1- _M(m) is postulated rather than sample-controlled. 3. Sample complexity to a structural floor. Under a shared-sample generative model and exponential decay, we establish a shared-oracle excess-to-floor sample-complexity guarantee for an averaged per-agent stationarity measure (Theorem 6): ~(ϵ−2) O(ε^-2) calls achieve excess ϵε above an explicit four-component structural floor, equivalently ~((τ−ϵfloor)−2) O((τ- _ floor)^-2) for a total target τ>ϵfloorτ> _ floor, under the unverified structural premises stated in Assumption Sets B, C, and D. A trajectory-conditional companion theorem (Theorem 7) gives a predictable-prefix bound, equivalently a stopped-process bound, which implies the corresponding global favorable-event bound, with a specialized reduction recorded for the zero-radius actor (Corollary 2). 4. Adaptive-locality diagnostic. We give a rule for selecting the locality radius at which the truncation and graph-decay residuals fall below the target accuracy (Proposition 4); this is reported as a bias-balancing diagnostic, not as a rate improvement. Scope. The guarantees are conditional on the stated assumption sets; TD-stability and smoothness premises are exhibited simultaneously here. The comparison with the smooth nonconvex lower bound is at the exponent level only: the oracle models differ, and no minimax-optimality claim is made. Table I summarizes the comparison with prior work; the displayed rates are not directly comparable across rows because the suppressed prefactors, floor structures, sampling models, and stationarity measures differ. TABLE I: Comparison with prior scalable networked multi-agent reinforcement learning methods. “Cond./diag.” describes the conditioning assumption and whether a sample-level diagnostic for the key conditioning constant is provided. “Cont.” indicates continuous state-action spaces. CDCPG rates are reported under the averaged projected-gradient-mapping stationarity measure as shared-oracle calls, stated to within a structural floor (Theorem 6, Remark 3). Rates are not directly comparable across rows because suppressed prefactors, floor structures, sampling models, and stationarity measures differ. Method Cond./diag. Cont. ϵε-Rate Sampling Qu et al. [22] structural postulate × ~(1/ϵ3) O(1/ε^3) indep. trajectories Lin et al. [17] structural postulate × ~(1/ϵ2) O(1/ε^2) generative Ren et al. [26] bounded-inverse postulate ✓ ~(1/ϵ2) O(1/ε^2) shared CDCPG (uniform) uniform TD-stability assumption ✓ ~(1/ϵ2) O(1/ε^2) to floor‡ shared CDCPG (traj.-cond.) trajectory TD-stability (assumed) + post-hoc certificate† ✓ ~(1/ϵ2) O(1/ε^2) to floor‡ shared †Assumption (C′) is a prospective premise. The matrix-Bernstein certificate (Proposition 3) provides a simultaneous post-hoc lower-confidence bound for the executed run, with false-certification probability at most δ; it does not by itself establish (C′), and a pilot run can only calibrate parameters, not certify the main trajectory. Neither certificate addresses the uniform-in- θ Assumption 4, which the uniform variant invokes purely as a hypothesis. ‡Displayed rate is the global shared-oracle count under the averaged projected-gradient-mapping stationarity measure; each shared sample is observed by every agent, so the same count applies to local observations per agent; no physical per-agent reduction by 1/n1/n is implied (Theorem 6). The remainder of the paper is organized as follows. Section I fixes notation, the networked MDP model and objective, and Assumption Sets A, B, and D. Section I develops the spectral framework and the RFF approximation. Section IV establishes exponential decay and the Q-function linear representation. Section V states the TD-stability Assumption Sets C and C′, once the population TD matrix they constrain has been defined, and presents the algorithm and the regularized LSTD analysis. Section VI states the complexity theorems. Section VII reports numerical experiments. Section VIII concludes. Proofs are in the appendix. I Preliminaries I-A Notation Vectors are bold lowercase, matrices bold uppercase, dI_d the identity, ∥⋅∥ · the Euclidean norm; σmin() _ (A) is the smallest singular value, λmin(),λmax() _ (A), _ (A) the extreme eigenvalues of symmetric A. The network is an undirected graph =([n],ℰ)G=([n],E) with maximum degree Δ≥2 ≥ 2; agent i’s κ-hop neighborhood is iκN_i^κ (i0=iN_i^0=\i\, i:=i1N_i:=N_i^1), Dκ:=maxi|iκ|D_κ:= _i |N_i^κ |, iκ,−:=[n]∖iκN_i^κ,-:=[n] N_i^κ. Local state spaces i=ℝdSS_i=R^d_S; local action spaces i⊆ℝdAA_i R^d_A are compact with diameter DAD_A; the joint spaces are :=∏iS:= _iS_i and :=∏iA:= _iA_i. Discount γ∈(0,1)γ∈(0,1). ~(g):=(gpolylog(g)) O(g):=O(g\,polylog(g)). Three locality radii are fixed throughout: κπ∈ℕ0 _π∈N_0 is the policy observation radius (each local policy observes iκπs_N_i _π; Assumption (A3) below), κ∈ℕκ∈N with κ≥max1,κπ+1κ≥ \1, _π+1\ is the critic truncation radius (the standing inequality is motivated in Definition 2), and κc:=κ+κπ _c:=κ+ _π is the gradient aggregation radius. I-B Networked model and problem statement The joint state is =(1,…,n)s=(s_1,…,s_n) and the joint action =(1,…,n)a=(a_1,…,a_n). The transition law factorizes across agents into local kernels, ℙ(′∣,)=∏i=1nℙi(i′∣i,i)P(s s,a)= _i=1^nP_i(s_i s_N_i,a_N_i), each agent receives a local reward ri(i,i)r_i(s_N_i,a_N_i), and the initial state is drawn as (0)∼μ0s^(0) _0; the Gaussian form of ℙiP_i and all regularity constants are imposed in Assumption Set A below. Policies are local and factorized, π(∣)=∏iπi(i∣iκπ;i)π(a s)= _i _i(a_i s_N_i _π; θ_i), with joint parameter =(1,…,n) θ=( θ_1,…, θ_n) ranging over a compact product set Θ0=∏iΘ0,i _0= _i _0,i specified in (A4). The local value and action-value functions under joint policy π are Viπ():=π[∑t=0∞γtri(i(t),i(t))|(0)=],Qiπ(,):=ri(i,i)+γ′∼ℙ[Viπ(′)]. aligned V_i^π(s)&:=E_π [ _t=0^∞γ^tr_i(s_N_i^(t),a_N_i^(t))\, |\,s^(0)=s ],\\ Q_i^π(s,a)&:=r_i(s_N_i,a_N_i)+γE_s P[V_i^π(s )]. aligned (1) The global objective is J():=(0)∼μ0[∑iViπ((0))]J( θ):=E_s^(0) _0[ _iV_i^π(s^(0))] with J∗:=sup∈Θ0J()J := _ θ∈ _0J( θ). Writing ℙtP_t for the law of (t)s^(t) under π started from μ0 _0, the discounted state occupancy and the state-action occupancy are dπ:=dμ0π:=(1−γ)∑t=0∞γtℙt,νπ:=dπ⊗π. aligned d^π:=d^π_ _0:=(1-γ) _t=0^∞γ^t\,P_t, ν^π:=d^π π. aligned (2) With Θ0 _0 compact, the ascent projected-gradient mapping η():=η−1(ΠΘ0(+η∇J())−) aligned G_η( θ):=η^-1 ( _ _0( θ+η∇ J( θ))- θ ) aligned (3) is the stationarity object: it coincides with ∇J()∇ J( θ) whenever the unprojected update +η∇J() θ+η∇ J( θ) remains in Θ0 _0, in particular in the unconstrained case, and ‖η‖≤‖∇J‖ G_η ≤ ∇ J pointwise by non-expansiveness of ΠΘ0 _ _0. Under (A4), the product structure Θ0=∏iΘ0,i _0= _i _0,i gives ΠΘ0(+η)=(ΠΘ0,i(i+ηi))i=1n _ _0( θ+ηv)=( _ _0,i( θ_i+ηv_i))_i=1^n, so Algorithm 1’s blockwise update equals the global projection step required by the convergence analysis. We measure progress by the averaged projected-gradient-mapping stationarity, n−1‖η()‖2≤ϵn^-1 G_η( θ) ^2≤ε, in agreement with the distributed-MARL convention [22, 17, 26]. This per-agent normalization is an exact rescaling of the aggregate mapping: for the averaged objective J/nJ/n with step size nηnη one has nηJ/n=η/nG^J/n_nη=G_η/n, hence n−1‖η‖2=n∥nηJ/n∥2n^-1 G_η ^2=n\, G^J/n_nη ^2; comparisons with generic complexity lower bounds are accordingly made at the level of the ϵε-exponent only. The policy gradient theorem [28] gives ∇J() ∇ J( θ) =11−γνπ[∑i=1nQiπ(,)∇logπ(∣)], = 11-γE_ν^π [ _i=1^nQ_i^π(s,a)\, _ θ π(a s) ], (4) with the occupancy pair (dπ,νπ)(d^π,ν^π) as defined above. Since π(∣)=∏jπj(j∣jκπ;j)π(a s)= _j _j(a_j s_N_j _π; θ_j) factorizes across agents and only πi _i depends on i θ_i, the per-agent gradient takes the form ∇iJ() _ θ_iJ( θ) =11−γνπ[∑ℓ=1nQℓπ(,)∇ilogπi(i∣iκπ)]. = 11-γE_ν^π [ _ =1^nQ_ ^π(s,a)\, _ θ_i _i(a_i s_N_i _π) ]. (5) This per-agent form is the basis of Algorithm 1’s gradient estimator, constructed in Section V. I-C Assumptions We group the assumptions into four sets. The model set A, the decay set B, and the sampling set D are stated here; the TD-stability sets C and C′ constrain the population temporal-difference matrix built from the critic features, and are therefore stated in Section V, immediately after that matrix has been defined. Assumption 1 (Set A: Model and regularity). (A1) Local dynamics i′=fi(i,i)+is_i =f_i(s_N_i,a_N_i)+ _i with fif_i deterministic, sup‖fi‖≤Bf f_i ≤ B_f, LfL_f-Lipschitz jointly in (i,i)(s_N_i,a_N_i), and i∼(,σ2dS) _i N(0,σ^2I_d_S) independent across i,ti,t. The initial distribution μ0 _0 is supported in :‖i‖≤B0∀i\s: s_i ≤ B_0\,∀ i\ for some B0<∞B_0<∞. (A2) Local rewards |ri(i,i)|≤r¯ |r_i(s_N_i,a_N_i) |≤ r, LrL_r-Lipschitz. (A3) Each local policy πi(⋅∣iκπ;i) _i(· s_N_i _π; θ_i) admits a density on iA_i, jointly measurable in the action, the local state, and the parameter, that is strictly positive a.e. on a fixed support isupp⊆iA_i supp A_i, common to all i∈Θ0,i θ_i∈ _0,i and all conditioning states. The policy is i θ_i-differentiable with score ∇ilogπi _ θ_i _i uniformly bounded by G, and is LπL_π-Lipschitz in Wasserstein-2 distance with respect to iκπs_N_i _π. The joint policy factors as π(∣)=∏iπi(i∣iκπ)π(a s)= _i _i(a_i s_N_i _π). (A4) The parameter space has a product structure Θ0=∏i=1nΘ0,i⊆ℝndθ _0= _i=1^n _0,i R^nd_θ, with each Θ0,i⊂ℝdθ _0,i⊂R^d_θ compact convex containing i(0) θ_i^(0), and global diameter DΘD_ . Under (A2), ViπV_i^π and QiπQ_i^π are uniformly bounded by Qmax:=r¯/(1−γ)Q_ := r/(1-γ); the map ↦J() θ J( θ) is continuous on Θ0 _0 under (A2)–(A3) by dominated convergence, so J∗J is attained on the compact Θ0 _0, and ΔJ:=J∗−J((0))≤2nQmax=(n) _J:=J -J( θ^(0))≤ 2nQ_ =O(n). An admissible policy class is a bounded-support, compactly parameterized exponential family satisfying (A3); concrete instances are policies whose sufficient statistics depend on the state through bounded or saturated local features, whereas policies with unbounded linear state features are admissible only after clipping or saturation. A tanh -squashed Gaussian satisfies the W2-Lipschitz inequality on Θ0 _0, but its score is unbounded near the action boundary in the absence of further truncation; we therefore adopt bounded-score parameterizations as the standing primitive. Assumption (A3) is invoked only to justify bounded-gradient policy-gradient concentration together with the locality and decay arguments; in particular, no uniform upper or lower bound on the policy density is imposed; only strict positivity on a fixed common support is required, which underwrites the log-density comparison in the continuity argument for the population TD matrix (Lemma 10). Relaxing it lies outside the present scope. Assumption 2 (Set B: Decay structure). (B2) Every policy in the considered class satisfies (c,ρ)(c,ρ)-exponential decay: for all i∈[n]i∈[n], κ∈ℕκ∈N, and (,),(′,′)(s,a),(s ,a ) agreeing on iκN_i^κ at the state-action level, |Qiπ(,)−Qiπ(′,′)|≤cρκ+1, aligned |Q_i^π(s,a)-Q_i^π(s ,a ) |≤ cρ^κ+1, aligned (6) with c,ρc,ρ independent of n,Tn,T. Set B contains the single decay item, labeled (B2) for cross-reference stability; the boundedness of the spectral splitting factor used by the feature construction is not assumed but derived explicitly from (A1) in Section I. Appendix A gives a heuristic contraction route (a sketch, not a proof) toward regimes in which (B2) is expected to hold; (B2) is assumed as a primitive in the main analysis. Other mechanisms include Dobrushin contraction of the joint chain [9, 25]. Assumption 3 (Set D: Sampling and smoothness). (D1) At each iteration k, a shared dataset s(k)D_s^(k) of MsM_s i.i.d. transitions (,,′,′)(s,a,s ,a ) with ∼dπ(k)s d^π^(k), ∼π(k)(⋅∣)a π^(k)(· s), ′∼ℙ(⋅∣,)s P(· s,a), ′∼π(k)(⋅∣′)a π^(k)(· s ) is drawn and shared across agents for LSTD; a separate shared dataset g(k)D_g^(k) of MgM_g pairs (,)∼dπ(k)⊗π(k)(s,a) d^π^(k) π^(k) is drawn for gradient estimation. The random-feature realization is sampled once at preprocessing and held fixed. (Local model access.) Each agent i knows the drift functions fjf_j for j∈iκc+κj∈N_i _c+κ, the reward functions rℓr_ for ℓ∈iκc ∈N_i _c, and the noise scale σ, and the random-feature draws of all ℓ∈iκc ∈N_i _c are reproducible from pseudorandom seeds broadcast once at preprocessing; these quantities are exactly what is needed to evaluate the augmented features of Definition 3 for agent i and its κc _c-neighbors. The feature construction is thus model-assisted: transition and reward functions are known locally, while the occupancy measure is accessed only through samples. (D2) J()J( θ) is LJL_J-smooth on Θ0 _0, i.e. ∇J∇ J is LJL_J-Lipschitz on Θ0 _0. We treat LJL_J as a primitive constant; under the additional regularity of (D3) below, LJL_J is moreover independent of the network size n, and Appendix B derives this n-uniformity from (D3). (D3) (Differentiated regularity, used only for the n-uniformity of LJL_J.) (i) Each local policy πi(⋅∣iκπ;i) _i(· s_N_i _π; θ_i) is twice continuously differentiable in i θ_i on Θ0,i _0,i, and the score ∇ilogπi _ θ_i _i is uniformly Lipschitz in i θ_i with constant G′G , uniformly over iκπs_N_i _π; under (A2)–(A3) and (i), J is then twice continuously differentiable on Θ0 _0 by dominated convergence (Appendix B, Step 0). (i) (Differentiated decay.) There exist constants c∂<∞c_∂<∞ and ρ∈(0,1)ρ∈(0,1) (the decay base of (B2)) such that the mixed parameter curvature of the objective decays geometrically in graph distance: for every pair i,ji,j and every ∈Θ0 θ∈ _0, ‖[∇2J()]ij‖≤c∂ρd(i,j), aligned [∇^2J( θ)]_ij ≤ c_∂\,ρ^\,d(i,j), aligned (7) where [∇2J]ij:=∂ij2J∈ℝdθ×dθ[∇^2J]_ij:=∂^2_ θ_i θ_jJ∈R^d_θ× d_θ is the cross-parameter Hessian block and d(i,j)d(i,j) is graph distance. This is the curvature analogue of the value-decay hypothesis (B2): whereas (B2) postulates that agent i’s value couples weakly to distant agents’ state-actions, (i) postulates that the cross-parameter curvature ∂ij2J∂^2_ θ_i θ_jJ couples agents i and j weakly at graph distance. It does not follow from (B2): differentiating the policy-gradient identity in j θ_j (Appendix B, Step 1) produces value-sensitivity, occupancy-sensitivity, and score-derivative terms whose combined decay involves mixed second-order differences that (B2) alone does not control. (i) The cross-parameter curvature decay (i) is summable over the bounded-degree graph: the standing graph-tail hypothesis δ~:=(Δ−1)ρ<1 δ:=( -1)ρ<1 holds. Sample counts in (D1) measure generative-oracle calls; realizing a call by geometric rollouts requires restart access to μ0 _0 and incurs an additional factor 1/(1−γ)1/(1-γ) in environment steps per sample. The n-uniformity of LJL_J in (D2)–(D3) is essential to the network-size scalability claim of Theorem 6; if LJL_J instead scales with n (for example, under a sum-of-values objective without the differentiated-decay structure of (D3)), the descent term of the complexity inherits the same scaling. Assumption (D3)(i) is a curvature counterpart of the exponential-decay hypothesis (B2): whereas (B2) controls the decay of QiπQ_i^π itself, (D3)(i) postulates the analogous geometric decay of the cross-parameter Hessian block ∂ij2J∂^2_ θ_i θ_jJ. We state it as a separate assumption because this decay does not follow from (B2) alone; Appendix B shows that (D3)(i), summed over the bounded-degree graph under the tail hypothesis (D3)(i), yields the n-uniform operator-norm bound on ∇2J∇^2J, and Appendix A sketches when (D3) is itself realizable under contraction conditions on the joint chain. Lemma 1 (Sub-Gaussian occupancy confinement). Under (A1) (whose bounded-support condition on μ0 _0 supplies the constant B0B_0), for any T∈ℕT∈N, δ∈(0,1)δ∈(0,1), ℙπ(sup0≤t≤T,i∈[n]‖i(t)‖≤DS(T,δ))≥1−δ, aligned P_π\! ( _0≤ t≤ T,\,i∈[n] s_i^(t) ≤ D_S(T,δ) )≥ 1-δ, aligned (8) with DS(T,δ):=maxB0,Bf+σ(dS+2log(n(T+1)/δ))D_S(T,δ):= \B_0,B_f+σ( d_S+ 2 (n(T+1)/δ))\, and confinement region Tδ:=:‖i‖≤DS(T,δ)∀iS_T^δ:=\s: s_i ≤ D_S(T,δ)\,∀ i\. The discounted-occupancy state marginal satisfies ℙ∼dπ(∈Tδ)≥1−δ−γT+1P_s d^π(s∈S_T^δ)≥ 1-δ-γ^T+1. Proof. By (A1), i(t+1)=fi(i(t),i(t))+i(t)s_i^(t+1)=f_i(s_N_i^(t),a_N_i^(t))+ _i^(t) with ‖fi‖≤Bf f_i ≤ B_f and i(t)∼(,σ2dS) _i^(t) N(0,σ^2I_d_S) independent across (i,t)(i,t). Standard Gaussian concentration [30, Thm. 2.6.3] gives ℙ(‖i(t)‖≤σ(dS+2u))≥1−e−uP( _i^(t) ≤σ( d_S+ 2u))≥ 1-e^-u. Setting u=log(n(T+1)/δ)u= (n(T+1)/δ) and union-bounding over i∈[n],0≤t≤Ti∈[n],0≤ t≤ T yields the displayed sup bound with probability ≥1−δ≥ 1-δ. The discounted-occupancy marginal bound follows from dπ=(1−γ)∑t=0∞γtℙtd^π=(1-γ) _t=0^∞γ^tP_t: contributions from t>Tt>T have total mass ∑t>T(1−γ)γt=γT+1 _t>T(1-γ)γ^t=γ^T+1, while contributions from t≤Tt≤ T are within TδS_T^δ with probability ≥1−δ≥ 1-δ. ∎ Throughout the paper we refer to this as “occupancy confinement” rather than “trajectory confinement,” because the algorithm uses generative-oracle samples from dπd^π at each iteration (Assumption (D1)), not a single physical trajectory. The lemma is used solely to control the discounted-occupancy mass outside the bounded region. I Spectral Representation Framework The local kernel ℙi(i′∣⋅)=k(i′−fi(⋅))P_i(s_i ·)=k(s_i -f_i(·)) with k()=(2πσ2)−dS/2exp(−‖2/(2σ2))k( )=(2πσ^2)^-d_S/2 (- ^2/(2σ^2)) is shift-invariant; the κ-neighborhood transition ℙi,κ=∏j∈iκℙjP_i,κ= _j∈N_i^κP_j admits a Bochner decomposition on the tensor-product Hilbert space. Let di,κ:=|iκ|⋅dSd_i,κ:= |N_i^κ |· d_S. For each i∈[n]i∈[n], draw an independent realization (i,ℓ,bi,ℓ)ℓ=1m\( ω_i, ,b_i, )\_ =1^m with i,ℓ∼(,σ−2di,κ) ω_i, N(0,σ^-2I_d_i,κ) and bi,ℓ∼Unif[0,2π]b_i, [0,2π]. Fix α∈(0,1)α∈(0,1) and define gα(i)(,) g_α^(i)(s,a) :=(2πσ2)−di,κ/2exp(α2‖i,κ‖22σ2(1−α2)), =(2πσ^2)^-d_i,κ/2 \! ( α^2 f_i,κ ^22σ^2(1-α^2) ), (9) pα(i)(iκ′) p_α^(i)(s_N_i^κ ) :=exp(−α2‖iκ′‖22σ2), = \! (- α^2 s_N_i^κ ^22σ^2 ), with i,κ:=(fj)j∈iκf_i,κ:=(f_j)_j∈N_i^κ, a function of the (κ+1)(κ+1)-neighborhood input :=(iκ+1,iκ+1)Z:=(s_N_i^κ+1,a_N_i^κ+1), giving the splitting identity ℙi,κ(iκ′∣⋅) P_i,κ(s_N_i^κ ·) (10) =gα(i)⋅pα(i)⋅k0(i,κ1−α2−1−α2iκ′), =g_α^(i)· p_α^(i)· k_0\! ( f_i,κ 1-α^2- 1-α^2\,s_N_i^κ ), k0()=exp(−‖2/(2σ2))k_0( )= (- ^2/(2σ^2)). Under (A1), ‖i,κ‖≤DκBf f_i,κ ≤ D_κB_f, so the splitting factor is explicitly and uniformly bounded: supi,gα(i)()≤g¯α(κ):=max1,(2πσ2)−1DκdS/2exp(α2DκBf22σ2(1−α2)), aligned & _i,Zg_α^(i)(Z)≤ g_α(κ):=\\ & \1,(2πσ^2)^-1\^D_κd_S/2 \! ( α^2D_κB_f^22σ^2(1-α^2) ), aligned (11) a derived bound (not an assumption) that is finite for fixed κ but exponential in the neighborhood dimension DκdSD_κd_S; this exponential dependence propagates into every feature-scale constant below and is the price of the spectral construction. Definition 1 (Normalized RFF). The raw RFF features are ϕi,κraw():=gα(i)()2m×cos(i,ℓ⊤i,κ()1−α2+bi,ℓ)ℓ=1m,μi,κraw():=pα(i)()2m×cos(1−α2i,ℓ⊤+bi,ℓ)ℓ=1m. aligned _i,κ raw(Z)&:=g_α^(i)(Z) 2m\\ & × \ \! ( ω_i, f_i,κ(Z) 1-α^2+b_i, ) \_ =1^m,\\ _i,κ raw(y)&:=p_α^(i)(y) 2m\\ & × \ \! ( 1-α^2\, ω_i, y+b_i, ) \_ =1^m. aligned (12) The normalized features ϕ^i,κ:=ϕi,κraw/g¯α φ_i,κ:= _i,κ raw/ g_α and ^i,κ:=μi,κrawg¯α μ_i,κ:= _i,κ raw g_α preserve the inner product and satisfy ‖ϕ^i,κ‖2≤2 φ_i,κ ^2≤ 2. The finite-feature approximant ⟨ϕ^i,κ,^i,κ⟩ φ_i,κ, μ_i,κ is a signed function and need not be a (sub)probability kernel; it enters the analysis only through its ℒ1L^1 distance to ℙi,κP_i,κ against bounded integrands. Theorem 1 (RFF approximation). Let g~α:=g¯αmax1,(2πσ2/α2)DκdS/2 g_α:= g_α \1,(2πσ^2/α^2)\^D_κd_S/2, R2(ϵP):=DκBf+(σ/α)(DκdS+2log(8g~α/ϵP))R_2( _P):= D_κB_f+(σ/α)( D_κd_S+ 2 (8 g_α/ _P)), and Dℛint(ϵP):=DκBf/1−α2+2R2(ϵP)D_R int( _P):= D_κB_f/ 1-α^2+2R_2( _P). For δrff∈(0,1) _ rff∈(0,1), ϵP∈(0,1] _P∈(0,1], if m m ≥CRFF(DκdS)g~α2ϵP2 ≥ C_ RFF(D_κd_S)\, g_α^2 _P^2 (13) ×log(212nDκdS(Dℛint(ϵP)g~α)2σ2ϵP2δrff), × \! ( 2^12\,n\,D_κd_S\, (D_R int( _P)\, g_α )^2σ^2\, _P^2\, _ rff ), where one may take CRFF(d)=16(d+2)C_ RFF(d)=16(d+2): the displayed constant–logarithm pair is exactly the sufficient condition derived in Appendix D (after substituting σp2=DκdS/σ2 _p^2=D_κd_S/σ^2); equivalently, CRFF(d)=C(d+2)C_ RFF(d)=C(d+2) for a universal C with any logarithm of the same order. Then the favorable RFF event Erff:=supi,∥ℙi,κ(⋅∣)−⟨ϕ^i,κ(),^i,κ(⋅)⟩∥ℒ1≤ϵP aligned E_ rff:= \ _i,Z P_i,κ(· Z)- φ_i,κ(Z), μ_i,κ(·) _L^1≤ _P \ aligned (14) satisfies ℙ(Erff)≥1−δrffP(E_ rff)≥ 1- _ rff. We define ϵP(m,δrff,n):=infϵP∈(0,1]:(13) holds _P(m, _ rff,n):= \ _P∈(0,1]: eq:rff_feasibility holds\; the required feature count on the right-hand side of (13) is strictly decreasing in ϵP _P on (0,1](0,1], so the feasible set is an interval and the infimum is well defined and attained whenever it is nonempty; with CRFF(d)=16(d+2)C_ RFF(d)=16(d+2) it satisfies ϵP(m)2=~(CRFF(DκdS)g~α2/m)=~(g~α2DκdS/m) _P(m)^2= O(C_ RFF(D_κd_S)\, g_α^2/m)= O( g_α^2D_κd_S/m). The random-feature dimension m is a problem primitive fixed before the target stationarity tolerance ϵε is sent to zero in Theorem 6. The proof (Appendix D) combines (i) the random-phase Rahimi–Recht uniform bound on a scaled compact core at tolerance ϵP/(2g~α) _P/(2 g_α), (i) integration of the weighted core error against the Gaussian factor pα(i)p_α^(i), (i) the true Gaussian-transition tail, and (iv) the tail of the signed approximant via the pointwise envelope 2gα(i)pα(i)2g_α^(i)p_α^(i); the derivation yields the explicit dimensional factor CRFF(d)=16(d+2)C_ RFF(d)=16(d+2). The intrinsic boundedness ‖i,κ‖≤DκBf f_i,κ ≤ D_κB_f from (A1) makes the conclusion global in Z. IV Exponential Decay and Q-Function Representation IV-A Exponential decay Lemma 2 (Value decay from Q-decay). Under (A3) and (B2), for κ≥κπ+1κ≥ _π+1 and any ,′s,s with iκ=iκ′s_N_i^κ=s _N_i^κ, |Viπ()−Viπ(′)|≤c~ρκ+1,c~:=2cρ−κπ. aligned |V_i^π(s)-V_i^π(s ) |≤ cρ^κ+1, c:=2cρ^- _π. aligned (15) The short proof is in Appendix E. IV-B Conditional-expectation truncated Q-function Definition 2 (Truncated Q-function). Let Xiκ:=(iκ,iκ)X_i^κ:=(S_N_i^κ,A_N_i^κ) denote the local state–action window, where capitalized symbols denote the corresponding random elements under νπν^π. Throughout assume κ≥max1,κπ+1κ≥ \1, _π+1\, so that XiκX_i^κ contains the reward inputs and the score-conditioning variables of agent i; the policy-conditioning variables of boundary agents in iκN_i^κ are integrated out through the marginal policy πiκmargπ marg_N_i^κ defined below. Define Q¯iπ() Q_i^π(x) :=νπ[Qiπ(,)|Xiκ=], =E_ν^π [Q_i^π(S,A)\, |\,X_i^κ=x ], (16) V¯iπ() V_i^π(s) :=dπ[Viπ()|iκ=], =E_d^π [V_i^π(S)\, |\,S_N_i^κ=s ], P¯i,κπ(d∣) P_i,κ^π(dy x) :=νπ[ℙi,κ(d∣iκ+1,iκ+1)∣Xiκ=], =E_ν^π[P_i,κ(dy S_N_i^κ+1,A_N_i^κ+1) X_i^κ=x], πiκmarg(d∣) π marg_N_i^κ(da s) :=νπ[πiκ(d∣)∣iκ=], =E_ν^π[ _N_i^κ(da S) S_N_i^κ=s], all a.s. elements of the appropriate ℒ∞L^∞ space; we fix bounded measurable representatives via regular conditional expectations. The conditional critic is tied to the objective’s initial distribution μ0 _0 through dπd^π; it is not claimed to be a statewise local Bellman object valid under every initial distribution. More precisely, let μi,κπ:=(iκ)#dπ _i,κ^π:=(S_N_i^κ)_\#d^π denote the local-state marginal of the discounted occupancy. The occupancy identity dπ=(1−γ)μ0+γℙπ⊤dπd^π=(1-γ) _0+γ\,P^π d^π gives ℙπ⊤dπ≤dπ/γP^π d^π≤ d^π/γ as measures, and this domination is preserved by the projection ↦iκs s_N_i^κ; hence every μi,κπ _i,κ^π-null set is null for the averaged successor law ∫P¯i,κπ(⋅∣)d[(Xiκ)#νπ]() P_i,κ^π(· x)\,d[(X_i^κ)_\#ν^π](x), so modifying V on a μi,κπ _i,κ^π-null set leaves ∫VdP¯i,κπ(⋅∣) V\,d P_i,κ^π(· x) unchanged for (Xiκ)#νπ(X_i^κ)_\#ν^π-a.e. x. Consequently T¯π T^π is well defined on ℒ∞(μi,κπ)L^∞( _i,κ^π)-equivalence classes and is a γ-contraction in the μi,κπ _i,κ^π-essential-supremum norm; the Banach fixed-point theorem is applied in that complete space, and a bounded measurable representative of the fixed point is selected once and used thereafter. The existence of regular conditional distributions follows since the state-action spaces are standard Borel; under the Gaussian transition structure of (A1), the relevant transition kernels also admit densities with respect to Lebesgue measure where needed. The auxiliary local Bellman operator (T¯πV)(iκ):=∼πiκmarg[ri+γ∫V()P¯i,κπ(d∣,)] aligned ( T^πV)(s_N_i^κ):=E_a π marg_N_i^κ [r_i+γ\! \!V(y)\, P_i,κ^π(dy s,a) ] aligned acts on bounded measurable representatives V∈Bb(iκ)V∈ B_b(S_N_i^κ), the space of bounded measurable functions on the local state neighborhood, where the integral ∫V()P¯i,κπ(d∣,) V(y) P_i,κ^π(dy s,a) is well-defined because P¯i,κπ(⋅∣,) P_i,κ^π(· s,a) admits a density with respect to Lebesgue measure (inherited from the Gaussian noise structure of (A1)). The operator T¯π T^π is a γ-contraction in the essential-supremum norm on this ℒ∞L^∞ space (equivalently, on bounded measurable representatives in Bb(iκ)B_b(S_N_i^κ) up to μi,κπ _i,κ^π-null modifications), and it maps the ball V:‖V‖∞≤r¯/(1−γ)\V: V _∞≤ r/(1-γ)\ to itself (since ‖T¯πV‖∞≤r¯+γ‖V‖∞≤r¯/(1−γ) T^πV _∞≤ r+γ V _∞≤ r/(1-γ) for ‖V‖∞≤r¯/(1−γ) V _∞≤ r/(1-γ)). Hence the unique fixed point V¯iπ,aux V_i^π, aux satisfies ‖V¯iπ,aux‖∞≤r¯/(1−γ) V_i^π, aux _∞≤ r/(1-γ). All subsequent equalities involving V¯iπ,aux V_i^π, aux and Q¯iπ Q_i^π are interpreted νπν^π-a.s. on chosen bounded measurable representatives. The two objects V¯iπ V_i^π and V¯iπ,aux V_i^π, aux are related via Proposition 1(b)’s residual. Convention. All suprema involving objects defined only νπν^π-a.e. are read as νπν^π-essential suprema on the relevant domain. For conditional objects defined as functions of XiκX_i^κ, the relevant measure is the pushforward (Xiκ)#νπ(X_i^κ)_\#ν^π, and the essential supremum is taken under this pushforward; the two are related by tower, (Xiκ)#νπ(X_i^κ)_\#ν^π-esssup|f|≤νπ *ess\,sup|f|≤ν^π-esssup|f∘Xiκ| *ess\,sup|f X_i^κ|. Outside the confinement region, the deterministic bounds furnished by the weight projection of Algorithm 1 are used only in the failure-event budget. Phrases such as “uniformly in s” and any ∥⋅∥∞ · _∞ applied to the conditional objects V¯iπ V_i^π, Q¯iπ Q_i^π, and P¯i,κπ P_i,κ^π are likewise read as essential-supremum bounds under the relevant local marginal or pushforward measure, evaluated for fixed bounded measurable representatives of the underlying regular conditional expectations. Proposition 1 (Approximation and auxiliary residual). Under (B2) and κ≥κπ+1κ≥ _π+1: (a) |Qiπ(,)−Q¯iπ(Xiκ)|≤cρκ+1 |Q_i^π(S,A)- Q_i^π(X_i^κ) |≤ cρ^κ+1 νπν^π-a.s. (b) There exists a residual RκR_κ with Q¯iπ()=ri()+γ∫V¯iπ,aux()P¯i,κπ(d∣)+Rκ(), aligned Q_i^π(x)=r_i(x)+γ\! \! V_i^π, aux(y)\, P_i,κ^π(dy x)+R_κ(x), aligned (17) and esssup|Rκ|≤γc~ρκ+1/(1−γ) *ess\,sup |R_κ |≤γ cρ^κ+1/(1-γ). Here ri()=ri(i,i)r_i(x)=r_i(s_N_i,a_N_i) is well-defined as a function of =(iκ,iκ)x=(s_N_i^κ,a_N_i^κ) because i⊆iκN_i N_i^κ under the standing hypothesis κ≥1κ≥ 1. IV-C Linear representation Definition 3 (Augmented features and weight). For =(iκ+1,iκ+1)z=(s_N_i^κ+1,a_N_i^κ+1), ϕ~i,κraw():=(ri(i,i),ϕ^i,κ())⊤∈ℝm+1,ϕ~i,κπ():=νπ[ϕ~i,κraw()∣Xiκ=], aligned φ_i,κ raw(z)&:= (r_i(s_N_i,a_N_i), φ_i,κ(z) ) ∈R^m+1,\\ φ_i,κ^π(x)&:=E_ν^π[ φ_i,κ raw(Z) X_i^κ=x], aligned (18) and the within-bin fluctuation i():=ϕ~i,κraw()−ϕ~i,κπ(Xiκ()) η_i(z):= φ_i,κ raw(z)- φ_i,κ^π(X_i^κ(z)), which satisfies [i∣Xiκ]=E[ η_i X_i^κ]=0 and ‖i‖≤2L η_i ≤ 2L pointwise, with L:=r¯2+2L:= r^2+2. The representation weight is i,κπ:=(1,γ∫^i,κ()V¯iπ,aux())⊤∈ℝm+1. aligned w_i,κ^π:= (1,\,γ\! \! μ_i,κ(y)\, V_i^π, aux(y)\,dy ) ∈R^m+1. aligned (19) For any coefficient vector ∈ℝm+1w∈R^m+1, the associated conditional-feature critic is Q¯i():=⟨ϕ~i,κπ(),⟩, aligned Q_i^w(x):= φ_i,κ^π(x),w , aligned (20) a function of the local variable =Xiκx=X_i^κ; this is the object whose error is controlled in Theorem 4. It is distinct from the critic implemented by Algorithm 1, which evaluates the raw augmented feature ϕ~i,κraw φ_i,κ raw directly, linearly and without value clipping, at the algorithm’s norm-projected coefficient; the two critics are compared in Lemma 7. Theorem 2 (Linear representation). Under Sets A–B with κ≥κπ+1κ≥ _π+1, on the favorable RFF event ErffE_ rff of Theorem 1 at accuracy ϵP _P, Q¯iπ()=⟨ϕ~i,κπ(),i,κπ⟩+ξi() aligned Q_i^π(x)= φ_i,κ^π(x),w_i,κ^π + _i(x) aligned (21) (Xiκ)#νπ(X_i^κ)_\#ν^π-a.e. on the local neighborhood domain iκ×iκS_N_i^κ×A_N_i^κ, with esssup|ξi|≤γr¯ϵP1−γ+γc~ρκ+11−γ=:ξ¯i. aligned *ess\,sup | _i |≤ γ r _P1-γ+ γ cρ^κ+11-γ=: ξ_i. aligned (22) The proof, in Appendix G, uses the global L1L^1-uniformity from Theorem 1 together with Proposition 1. V Algorithm and LSTD Analysis V-A Population TD matrix and stability assumptions The raw-feature population objects at parameter θ are i:=i−γi,M_i θ:=H_i θ-γC_i θ, (23) with i:=[ϕ~raw()ϕ~raw()⊤]H_i θ:=E[ φ raw(Z) φ raw(Z) ], i:=[ϕ~raw()ϕ~raw(′)⊤]C_i θ:=E[ φ raw(Z) φ raw(Z ) ], and i:=[ϕ~raw()ri]b_i θ:=E[ φ raw(Z)r_i], where the expectations are under ∼νπZ ν _ θ and ′Z drawn one transition forward. Assumption 4 (Set C: TD stability). Define the event EM:=σmin(i)≥μM(m)>0,∀i∈[n],∀∈Θ0, aligned E_M:= \ _ (M_i θ)≥ _M(m)>0,\ ∀ i∈[n],\,∀ θ∈ _0 \, aligned (24) where iM_i θ is the raw-feature TD matrix (23). There is a constant δM(m)∈(0,1) _M(m)∈(0,1) such that ℙ(EM)≥1−δM(m)P(E_M)≥ 1- _M(m). Three remarks delimit the scope of Set C. First, EME_M is measurable: under (A1) and (A3), ↦i θ M_i θ is continuous on the compact Θ0 _0 (Lemma 10, Appendix C), so the infimum over Θ0 _0 reduces to one over a countable dense subset. Second, the notation suppresses dependencies: μM _M and δM _M may depend not only on m but also on n, κ, the graph, and the policy class Θ0 _0; in particular, with independent per-agent feature draws a per-agent failure probability δM(1) _M^(1) compounds by a union bound to δM≤nδM(1) _M≤ n\, _M^(1). Third, the confidence 1−δM(m)1- _M(m) is postulated, not user-controllable: unlike δrff _ rff, it cannot be driven to zero by enlarging a sample size; a practical (not theoretical) control is to redraw the feature realization and re-test conditioning via the diagnostic of Proposition 3. Lemma 3 below reduces (C) to a symmetric feature-excitation condition. The m-dependence of μM _M is necessary: Proposition 2 (Dimensional obstruction to dimension-free TD-stability). For any TD matrix i=[ϕ~raw()(ϕ~raw()−γϕ~raw(′))⊤]M_i θ=E[ φ raw(Z)( φ raw(Z)-γ φ raw(Z )) ] generated by features with ‖ϕ~raw‖≤L φ raw ≤ L a.s. and lying in ℝm+1R^m+1, σmin(i)≤‖i‖Fm+1≤(1+γ)L2m+1→m→∞0, aligned _ (M_i θ)≤ M_i θ _F m+1≤ (1+γ)L^2 m+1 m→∞0, aligned (25) so no dimension-free lower bound μM _M exists; accordingly the analysis below operates in the fixed-m regime and treats m as a problem primitive. This is the only general upper bound on σmin(i) _ (M_i θ) established in this paper; no (1/m)O(1/m) upper bound is proved. Lemma 3 (Excitation implies TD stability). Under (A1)–(A3) and the occupancy sampling of (D1), for every i∈[n]i∈[n], every ∈Θ0 θ∈ _0, and every feature realization: whenever i≻H_i θ 0, the whitened cross term obeys the unconditional bound ‖i,−1/2ii,−1/2‖2≤γ−1/2 H_i θ,-1/2C_i θH_i θ,-1/2 _2≤γ^-1/2, and consequently σmin(i)≥(1−γ)λmin(i). aligned _ (M_i θ)\;≥\;(1- γ)\, _ (H_i θ). aligned (26) Hence the symmetric feature-excitation condition λmin(i)≥hM(m)>0 _ (H_i θ)≥ h_M(m)>0 for all i∈[n]i∈[n] and ∈Θ0 θ∈ _0, on an event of probability ≥1−δM(m)≥ 1- _M(m) over the feature draw, implies Assumption (C) with μM(m)=(1−γ)hM(m) _M(m)=(1- γ)\,h_M(m). Proof. Fix i,i, θ and the feature realization, and abbreviate :=iH:=H_i θ, :=iC:=C_i θ, :=iM:=M_i θ. Let ν:=νπν:=ν _ θ and let ν+ _+ denote the law of the successor pair ′Z under the one-step law of (D1). The occupancy identity dπ=(1−γ)μ0+γℙπ⊤dπd^π=(1-γ) _0+γ\,P^π d^π gives ℙπ⊤dπ≤dπ/γP^π d^π≤ d^π/γ as measures, hence ν+=(ℙπ⊤dπ)⊗π≤ν/γ _+=(P^π d^π) _ θ≤ν/γ, and therefore the successor feature covariance +:=ν+[ϕ~rawϕ~raw⊤]H_+:=E_ _+[ φ raw φ raw ] satisfies ⊤+=∫(⊤ϕ~raw)2ν+≤γ−1∫(⊤ϕ~raw)2ν=γ−1⊤u H_+u= (u φ raw)^2\,d _+≤γ^-1 (u φ raw)^2\,dν=γ^-1u Hu for every u, i.e. +⪯/γH_+ H/γ. For unit vectors ,u,v, Cauchy–Schwarz under the joint one-step law gives |⊤−1/2−1/2|≤((⊤−1/2ϕ~raw())2)1/2×((⊤−1/2ϕ~raw(′))2)1/2=(⊤−1/2+−1/2)1/2≤γ−1/2. aligned |u H^-1/2CH^-1/2v |&≤ (E(u H^-1/2 φ raw(Z))^2 )^1/2\\ & × (E(v H^-1/2 φ raw(Z ))^2 )^1/2\\ &= (v H^-1/2H_+H^-1/2v )^1/2≤γ^-1/2. aligned Writing =1/2(−γ)1/2M=H^1/2(I-γB)H^1/2 with :=−1/2−1/2B:=H^-1/2CH^-1/2 and using σmin()≥σmin()σmin()σmin() _ (XYZ)≥ _ (X)\, _ (Y)\, _ (Z) for square matrices, σmin()≥λmin()σmin(−γ)≥λmin()(1−γ‖)≥(1−γ)λmin() _ (M)≥ _ (H)\, _ (I-γB)≥ _ (H)(1-γ B )≥(1- γ) _ (H). If λmin()=0 _ (H)=0 the displayed bound holds trivially. ∎ Lemma 3 upgrades the classical excitation-versus-contraction heuristic to a theorem: the cross-term bound β≤γ−1/2β≤γ^-1/2, which earlier formulations had to assume, is here derived from the discounted-occupancy identity, so TD stability reduces to excitation of a symmetric covariance, a persistence-of-excitation condition standard in adaptive control [20], monitorable through λmin _ of the empirical PSD matrix ^i(k) H_i^(k) by the same matrix-Bernstein radius as in Proposition 3. The route remains a certificate with a dimensional cap: tr(i)=‖ϕ~raw‖2≤L2tr(H_i θ)=E φ raw ^2≤ L^2 forces λmin(i)≤L2/(m+1) _ (H_i θ)≤ L^2/(m+1), so the excitation certificate is at most (1−γ)L2/(m+1)(1- γ)L^2/(m+1); this is consistent with, and not an upper bound beyond, Proposition 2; the true σmin(i) _ (M_i θ) may exceed it, and the only proved general upper bound on the true conditioning remains the (m−1/2)O(m^-1/2) of that proposition. Verifying the excitation bound hM(m)>0h_M(m)>0 for a concrete continuous networked model class is left open; a uniform lower policy density on the compact action sets would be the natural tool for such a verification on a compact core, and is deliberately not imposed here because the present analysis assumes, rather than verifies, the bound. For some results we use the strictly weaker trajectory-conditional version of (C): Assumption 5 (Set C′: Trajectory-conditional stability). There exists μtraj>0 _ traj>0 such that inf0≤k<K,i∈[n]σmin(i(k))≥μtraj aligned _0≤ k<K,\,i∈[n] _ (M_i θ^(k))≥ _ traj aligned (27) holds with probability at least 1−δMtraj1- _M traj, where the probability is over the random-feature realization at preprocessing and the realized algorithmic sample path s(k),g(k)k<K\D_s^(k),D_g^(k)\_k<K jointly. The empirical proxy σmin(i(k)) _ (M_i^(k)) (Theorem 3) controls (C′) at high probability on the realized trajectory via matrix-Bernstein concentration in the false-certification sense (Proposition 3); it does not certify the uniform infimum (C). The paper provides both a (C)-based theorem and a (C′)-based companion theorem. V-B Regularized LSTD Definition 4 (LSTD matrices). With (j)=(iκ+1(j),iκ+1(j))z^(j)=(s_N_i^κ+1^(j),a_N_i^κ+1^(j)) and the one-step successor ′(j)=(iκ+1′(j),iκ+1′(j))z (j)=(s_N_i^κ+1 (j),a_N_i^κ+1 (j)) from s(k)D_s^(k), i(k):=1Ms∑j=1Msϕ~i,κraw((j))×(ϕ~i,κraw((j))−γϕ~i,κraw(′(j)))⊤,i(k):=1Ms∑j=1Msri(j)ϕ~i,κraw((j)). aligned M_i^(k)&:= 1M_s\! _j=1^M_s\! φ_i,κ raw(z^(j))\\ & × ( φ_i,κ raw(z^(j))\!-\!γ φ_i,κ raw(z (j)) )^\! \!\!,\\ b_i^(k)&:= 1M_s\! _j=1^M_sr_i^(j)\, φ_i,κ raw(z^(j)). aligned (28) The regularized LSTD solution is ^i(k),raw:=(i(k)+λ)−1i(k) w_i^(k), raw:=(M_i^(k)+λI)^-1b_i^(k) whenever i(k)+λM_i^(k)+λI is non-singular, and ^i(k),raw:= w_i^(k), raw:=0 in the degenerate (singular) case. This degenerate fallback agrees with Algorithm 1, line 5. The analysis invokes the inverse only on favorable events, collected in the Randomness subsection below, where the singular-value lower bound σmin(i(k)+λ)≥μM/2 _ (M_i^(k)+λI)≥ _M/2 holds, so the matrix is non-singular and the degenerate fallback is not triggered. Outside those events the implemented algorithm continues to produce an output via the norm projection (Algorithm 1, line 6), and the analysis invokes only the resulting deterministic bounds ‖^i(k)‖≤W∗ w_i^(k) ≤ W and hence |Q^i(k)|≤LW∗ | Q_i^(k) |≤ LW , with W∗W the deterministic projection radius fixed in Lemma 5 below. Because the same zero fallback is used in both the definition and the algorithm, the estimator analyzed in the theorems below coincides exactly, on every sample path, with the estimator implemented in Algorithm 1. Define the population-target ceiling U1:=1+2γg~αr¯/(1−γ)U_1:=1+ 2γ g_α r/(1-γ); Appendix I (Step 1) shows ‖i,κπ‖≤U1 w_i,κ^π ≤ U_1. Lemma 4 (Conditional projection error). Conditional on EM∩ErffE_M∩ E_ rff, the population LSTD solution i∗:=(i)−1iw_i :=(M_i θ)^-1b_i θ satisfies ‖i∗−i,κπ‖≤(1+γ)Lξ¯iaug+Lγcρκ+1μM+Cη(1+2γ)L2‖i,κπ‖μM, aligned w_i -w_i,κ^π ≤ (1+γ)L ξ_i aug+Lγ cρ^κ+1 _M+ C_η(1+2γ)L^2 w_i,κ^π _M, aligned (29) where ξ¯iaug:=ξ¯i+Eout ξ_i aug:= ξ_i+E_ out collects the on-confinement linear-representation residual and the outside-confinement contribution Eout:=(Qmax+LU1)(1+1/γ)(δtraj+γT+1)E_ out:=(Q_ +LU_1)(1+1/γ)( _ traj+γ^T+1), with U1U_1 the population-target ceiling defined above, and Cη≤4C_η≤ 4 is universal. The explicit Bellman-defect term Lγcρκ+1/μMLγ cρ^κ+1/ _M is retained in the statement in weight units; in the proof of Theorem 4 it is multiplied by the feature norm L to convert it to Q-error units, and the resulting contribution L2γcρκ+1/μML^2γ cρ^κ+1/ _M is absorbed into the C′Etrunc(κ)C E_ trunc(κ) floor term, leaving the downstream constant C′=(1+γ)L2/μMC =(1+γ)L^2/ _M unchanged. On the confinement layer. Theorem 1 is global in Z (its kernel-argument domain is compact independently of the state, since ‖i,κ‖≤DκBf f_i,κ ≤ D_κB_f), so the representation residual itself does not require confinement. The confinement region and the term EoutE_ out are retained, conservatively, because the deterministic pointwise bounds used in the failure-event budget (Lemma 7 and the target-radius construction of Lemma 5) are stated with confinement-region control; all constants (W∗,δ⋆,TW , _ ,T) are fixed from primitives before the run, so no circular dependency arises in Theorem 3’s use of ‖i∗‖≤W∗ w_i ≤ W . Removing the layer, which would eliminate δtraj _ traj, T, EoutE_ out, and the corresponding side condition in ϵ0 _0, is a simplification that we flag but do not undertake here, as it would require re-deriving the budget bounds throughout. Lemma 5 (Projection radius and no-circularity). Define W0 W_0 :=KbinU1+2Lγr¯ϵP(1−γ)μM+8Lc~ρκ+1(1−γ)μM, =K_ binU_1+ 2Lγ r _P(1-γ) _M+ 8L cρ^κ+1(1-γ) _M, (30) Kbin K_ bin :=1+Cη(1+2γ)L2/μM, =1+C_η(1+2γ)L^2/ _M, and fix the projection radius of Algorithm 1 as the deterministic constant W∗:=2W0W :=2W_0, which depends only on the primitives (L,γ,r¯,g~α,c~,ρ,κ,μM,ϵP)(L,γ, r, g_α, c,ρ,κ, _M, _P); in particular, it does not depend on the target tolerance ϵε, on δtraj _ traj or T, or on any random quantity. Conditional on EM∩ErffE_M∩ E_ rff and under the side condition δtraj+γT+1≤μMW0/[(1+γ)L(Qmax+LU1)(1+1/γ)] _ traj+γ^T+1≤ _MW_0/[(1+γ)L(Q_ +LU_1)(1+1/γ)], enforced by the parameter choices below, the population LSTD solution satisfies ‖i∗‖≤W0+(1+γ)LEout/μM≤2W0=W∗ w_i ≤ W_0+(1+γ)LE_ out/ _M≤ 2W_0=W . Off the favorable events, the analysis uses only the deterministic bounds ‖^i(k)‖≤W∗ w_i^(k) ≤ W (norm projection) and hence |Q^i(k)|≤LW∗ | Q_i^(k) |≤ LW . Theorem 3 (LSTD concentration, fixed-(i,k)(i,k)). Under Sets A–D, conditional on EM∩ErffE_M∩ E_ rff, for fixed i∈[n]i∈[n] and k<Kk<K, any δ∈(0,1)δ∈(0,1) and λ∈[0,μM/4]λ∈[0, _M/4], if Ms≥C0L4log((m+1)/δ)/μM2M_s≥ C_0L^4 ((m+1)/δ)/ _M^2, then with probability ≥1−δ≥ 1-δ over s(k)D_s^(k), ‖^i(k),raw−i∗((k))‖≤2CvL(r¯+(1+γ)LW∗)μMlog((m+1)/δ)Ms+2λW∗μM. aligned & w_i^(k), raw-w_i ( θ^(k)) \\ & ≤ 2C_vL( r+(1+γ)LW ) _M ((m+1)/δ)M_s+ 2λ W _M. aligned The uniform version over all i∈[n]i∈[n], k<Kk<K holds with δ replaced by δ/(nK)δ/(nK). Here C0,Cv>0C_0,C_v>0 are universal constants arising from the matrix-Bernstein and vector Hoeffding inequalities used in the proof. The proof (Appendix J) uses matrix-Bernstein on i(k)−i(k)M_i^(k)-M_i θ^(k) via Hermitian dilation, since the matrix is non-symmetric, and a finite-dimensional Hilbert-space Hoeffding-type inequality [21, Thm. 3.5] for the centered vector i(k)−i(k)i∗b_i^(k)-M_i^(k)w_i , which gives a dimension-free vector deviation; the displayed log(m+1) (m+1) factor is retained only as a harmless upper bound for compatibility with the matrix-Bernstein term. Since ‖i∗‖≤W∗ w_i ≤ W (Lemma 5), non-expansiveness of the norm projection gives ‖^i(k)−i∗‖≤‖^i(k),raw−i∗‖ w_i^(k)-w_i ≤ w_i^(k), raw-w_i , so the bound transfers verbatim to the projected coefficient used by the algorithm. We write Elstdi,kE_ lstd^i,k for the event of Theorem 3 at confidence δlstd _ lstd. Remark 1 (Role of λλI under non-symmetric iM_i θ). The TD matrix iM_i θ is generally non-symmetric, so the additive term λλI does not act as a positive-definite ridge that would unambiguously improve conditioning. For non-self-adjoint M, σmin(+λ) _ (M+λI) is not equal to σmin()+λ _ (M)+λ and may decrease with λ. In the derived bound of Theorem 3, λ contributes a pure additive bias with no compensating benefit: the statistical term does not improve with λ, and on the favorable events invertibility is supplied by concentration, not by regularization. Accordingly the parameter selection of Theorem 4 takes λ∗=0λ =0. A positive λ is retained in Algorithm 1 only as an implementation option whose additive bias 2λW∗/μM2λ W / _M is retained explicitly in Theorem 3; it is not a conditioning safeguard, since for a non-normal matrix the shift λλI can decrease σmin _ ; near-singularity is instead handled by the singular-value threshold of Algorithm 1, line 5, whose numerical tolerance may be tied to the concentration radius rMr_M of Proposition 3. When λ>0λ>0 is used, it is subject to the side condition λ≤μM/4λ≤ _M/4 under which the singular-value lower bound used in the proof, the reverse-triangle bound σmin(i(k)+λ)≥σmin(i(k))−‖i(k)−i(k)‖−λ, aligned _ (M_i^(k)+λI)≥ _ (M_i θ^(k))- M_i^(k)-M_i θ^(k) -λ, aligned (31) remains meaningful. Setting λ larger does not improve invertibility of the non-symmetric design matrix. V-C Randomness and events The analysis distinguishes three favorable events and one small-mass region: EME_M (TD-stability, Assumption 4, probability ≥1−δM(m)≥ 1- _M(m) over the random-feature draw), ErffE_ rff (RFF uniform approximation, probability ≥1−δrff≥ 1- _ rff), Elstdi,kE_ lstd^i,k (per-iteration LSTD concentration, probability ≥1−δlstd≥ 1- _ lstd over s(k)D_s^(k) conditional on past randomness and EM∩ErffE_M∩ E_ rff; formalized after Theorem 3), and the confinement region TδtrajS_T _ traj of Lemma 1, whose complement carries discounted-occupancy mass at most δtraj+γT+1 _ traj+γ^T+1 (a per-sample region membership entering only through expectations, not a global sample event; the symbol EoccE_ occ is used for it purely as bookkeeping). We use two filtrations to make conditional sampling claims precise. Let ℱRFF:=σ(i,ℓ,bi,ℓi,ℓ)F_ RFF:=σ (\ ω_i, ,b_i, \_i, ) collect the preprocessing randomness. Then ℱk−:=σ(ℱRFF,(0),s(j),g(j)j<k,(k)),ℱkQ:=σ(ℱk−,s(k),^i(k)i∈[n]). aligned F_k^-&:=σ (F_ RFF,\, θ^(0),\,\D_s^(j),D_g^(j)\_j<k,\, θ^(k) ),\\ F_k^Q&:=σ (F_k^-,\,D_s^(k),\,\ w_i^(k)\_i∈[n] ). aligned (32) Under (D1), s(k)D_s^(k) is i.i.d. from the joint one-step law dπ(k)⊗π(k)⊗ℙ⊗π(k)d _ θ^(k) _ θ^(k) P _ θ^(k) generating (,,′,′)(s,a,s ,a ), conditional on ℱk−F_k^-, and g(k)D_g^(k) is i.i.d. from dπ(k)⊗π(k)d _ θ^(k) _ θ^(k) conditional on ℱkQF_k^Q. The shorthand ℱ(k)F^(k) when used without superscript refers to ℱk−F_k^- for LSTD-side statements and ℱkQF_k^Q for gradient-side statements; the context disambiguates. Theorems below are conditional on the preprocessing favorable events EM∩Erff∈ℱRFFE_M∩ E_ rff∈F_ RFF, with total failure budget summed over the listed events. V-D Joint parameter selection Define Etrunc(κ):=c~ρκ+1(1+21−γ),Erff(m):=γr¯ϵP(m,δrff,n)1−γ,C′:=(1+γ)L2/μM,Cbin:=Cη(1+2γ)L3U1/μM. aligned E_ trunc(κ)&:= cρ^κ+1 (1+ 21-γ ),\\ E_ rff(m)&:= γ r _P(m, _ rff,n)1-γ,\\ C &:=(1+γ)L^2/ _M,\\ C_ bin&:=C_η(1+2γ)L^3U_1/ _M. aligned (33) The constant CbinC_ bin uses U1U_1 (the population-target ceiling defined before Lemma 4) rather than W∗W because the within-bin term in Lemma 4 multiplies ‖i,κπ‖≤U1 w_i,κ^π ≤ U_1, not the LSTD-solution norm. Using W∗≥U1W ≥ U_1 in place of U1U_1 inflates the floor and is permissible but conservative; we adopt the sharper U1U_1 form. Lemma 6 (Exact within-bin matrix gap). Let ¯i:=[ϕ~i,κπ(X)(ϕ~i,κπ(X)−γϕ~i,κπ(X′))⊤] M_i θ:=E[ φ_i,κ^π(X)( φ_i,κ^π(X)-γ φ_i,κ^π(X )) ] denote the conditional-feature TD matrix, with X:=Xiκ()X:=X_i^κ(Z), X′:=Xiκ(′)X :=X_i^κ(Z ), and i′:=i(′) η_i := η_i(Z ). Then, using [i∣X]=E[ η_i X]=0 and X-measurability of ϕ~i,κπ(X) φ_i,κ^π(X), i,κ:=i−¯i=[ii⊤]−γ[ii′⊤]−γ[iϕ~i,κπ(X′)⊤]−γ[ϕ~i,κπ(X)i′⊤], aligned _i,κ θ&:=M_i θ- M_i θ=E[ η_i η_i ]-γ\,E[ η_i η_i ]\\ & -γ\,E[ η_i\, φ_i,κ^π(X ) ]-γ\,E[ φ_i,κ^π(X)\, η_i ], aligned and, with v02:=supi,νπ‖i‖2v_0^2:= _i, θE_ν _ θ η_i ^2 and v+2:=supi,‖i′‖2≤v02/γv_+^2:= _i, θE η_i ^2≤ v_0^2/γ (by the occupancy domination noted in Definition 2), ‖i,κ‖≤(1+γ)v0(v0+γL). aligned _i,κ θ \;≤\;(1+ γ)\,v_0\,(v_0+ γ\,L). aligned (34) This bound is (L2)O(L^2) in general (since v0≤2Lv_0≤ 2L) and may replace the generic constant Cη(1+2γ)L2C_η(1+2γ)L^2 in the within-bin term of Lemma 4 whenever it is smaller, with CbinC_ bin correspondingly replaced by LU1supi,‖i,κ‖/μML\,U_1 _i, θ _i,κ θ / _M. When iκ=[n]N_i^κ=[n] for all i (full locality), i≡ η_i≡0, so i,κ= _i,κ θ=0 exactly and this floor contribution vanishes; the generic envelope used in the headline constants does not vanish there and is, in that regime, purely an upper-bound artifact. The same qualification applies to the truncation and aggregation contributions: at full locality the underlying errors are identically zero, while the exponential envelopes remain positive as stated (Etrunc(κ)E_ trunc(κ) above, and the aggregation envelope ϵagg(κ) _ agg(κ) defined in Lemma 8). Proof. Write ϕ~raw()=ϕ~i,κπ(X)+i φ raw(Z)= φ_i,κ^π(X)+ η_i and ϕ~raw(′)=ϕ~i,κπ(X′)+i′ φ raw(Z )= φ_i,κ^π(X )+ η_i and expand iM_i θ; the two cross terms [iϕ~i,κπ(X)⊤]E[ η_i φ_i,κ^π(X) ] and [ϕ~i,κπ(X)i⊤]E[ φ_i,κ^π(X) η_i ] vanish by tower against σ(X)σ(X), yielding the display. For the norm bound: ‖[ii⊤]‖≤‖i‖2≤v02 E[ η_i η_i ] ≤E η_i ^2≤ v_0^2; |⊤[ii′⊤]|≤((⊤i)2)1/2((⊤i′)2)1/2≤v0v+ |u E[ η_i η_i ]v |≤(E(u η_i)^2)^1/2(E(v η_i )^2)^1/2≤ v_0v_+; and the two mixed terms are bounded by Lv0Lv_0 and Lv+Lv_+ using the pointwise bound ‖ϕ~i,κπ‖≤L φ_i,κ^π ≤ L. Since the successor law is dominated by νπ/γν _ θ/γ (Definition 2), v+≤v0/γv_+≤ v_0/ γ; collecting terms with γv+≤γv0γ v_+≤ γ\,v_0 gives ‖i,κ‖≤(1+γ)v02+γ(1+γ)Lv0=(1+γ)v0(v0+γL) _i,κ θ ≤(1+ γ)v_0^2+ γ(1+ γ)Lv_0=(1+ γ)\,v_0\,(v_0+ γL). ∎ Theorem 4 (Local parameter selection). Under Sets A–D with κ≥κπ+1κ≥ _π+1 and m satisfying (13) at confidence δrff _ rff, fix i∈[n]i∈[n] and k<Kk<K; choose ϵQ>0 _Q>0, δ⋆∈(0,1) _ ∈(0,1), T∈ℕT∈N, δtraj∈(0,1) _ traj∈(0,1), and suppose ϵQ≤LW∗ _Q≤ LW . With the parameter choices λ∗=0,Ms∗=~(L6W∗2/(μM2ϵQ2)), aligned λ &=0,\\ M_s &= O(L^6W 2/( _M^2 _Q^2)), aligned (35) conditional on EM∩ErffE_M∩ E_ rff, with probability ≥1−δ⋆≥ 1- _ over s(k)D_s^(k), esssupνπonTδtraj×|Q¯i^i(k)(Xiκ(,))−Qiπ(,)| *ess\,sup_ν^π\, on\,S_T _ traj×A | Q_i w_i^(k)(X_i^κ(s,a))-Q_i^π(s,a) | (36) ≤ϵQ+R(κ,m)+C′Eout, ≤ _Q+R(κ,m)+C E_ out, where R(κ,m):=(1+C′)(Etrunc(κ)+Erff(m))+CbinR(κ,m):=(1+C )(E_ trunc(κ)+E_ rff(m))+C_ bin, with the local-to-global lift handled via Proposition 1(a). The total unconditional failure probability is δM+δrff+δ⋆ _M+ _ rff+ _ . A uniform version over i∈[n]i∈[n] and k<Kk<K follows by replacing δ⋆ _ with δ⋆/(nK) _ /(nK). With λ∗=0λ =0 the regularization bias vanishes and the full budget is assigned to the statistical term, giving Estat≤ϵQE_ stat≤ _Q; the standing hypothesis ϵQ≤LW∗ _Q≤ LW ensures that any positive implementation value λ≤μMϵQ/(4LW∗)λ≤ _M _Q/(4LW ), which adds bias at most ϵQ/2 _Q/2, also satisfies the side condition λ≤μM/4λ≤ _M/4 of Remark 1. V-E Distributed policy gradient Recall from Section I the aggregation radius κc=κ+κπ _c=κ+ _π and the standing inequality κ≥κπ+1κ≥ _π+1. The gradient estimator at agent i, derived from the per-agent policy-gradient identity (5), is ^i(k) g_i^(k) :=1(1−γ)Mg∑j=1MgQ^i,κc(k)((j),(j)) = 1(1-γ)M_g\! _j=1^M_g\! Q_i, _c^(k)(s^(j),a^(j)) (37) ⋅∇ilogπi(i(j)∣iκπ(j)), · _ θ_i _i(a_i^(j) s_N_i _π^(j)), with Q^i,κc(k)(,):=∑ℓ∈iκcQ^ℓ(k)(ℓκ+1,ℓκ+1) Q_i, _c^(k)(s,a):= _ ∈N_i _c Q_ ^(k)(s_N_ ^κ+1,a_N_ ^κ+1) and Q^ℓ(k)():=ϕ~ℓ,κraw()⊤^ℓ(k) Q_ ^(k)(z):= φ_ ,κ raw(z) w_ ^(k), so that |Q^ℓ(k)|≤LW∗ | Q_ ^(k) |≤ LW deterministically by the norm projection. No value clipping is applied: keeping the deployed critic linear in the raw feature is what validates the κπ=0 _π=0 tower cancellation of Lemma 8 and Corollary 2; a nonlinearity such as clipping would break the conditional-mean argument. Here and below, algE_ alg denotes expectation over the algorithmic sampling randomness of the current iteration that produces the critic coefficient ^i(k) w_i^(k) (the LSTD sample set s(k)D_s^(k)), taken conditional on the preprocessing favorable events EM∩ErffE_M∩ E_ rff and the current iterate (k) θ^(k). Lemma 7 (Critic L2L^2 error). Under the conditions of Theorem 4 with δ⋆=δtraj=ϵQ2/(3(LW∗+Qmax)2) _ = _ traj= _Q^2/(3(LW +Q_ )^2) and the truncation horizon T=⌈log(1/δ⋆)/log(1/γ)⌉−1T= (1/ _ )/ (1/γ) -1 taken as the smallest integer with γT+1≤δ⋆γ^T+1≤ _ , algνπ[|Q^i(k)−Qiπ|2]≤3ϵQ2+2Rtot(κ,m)2, aligned E_ algE_ν^π\! [ | Q_i^(k)-Q_i^π |^2 ]≤ 3 _Q^2+2R_ tot(κ,m)^2, aligned (38) where Rtot(κ,m):=2[R(κ,m)+C′Eout]+2LW∗R_ tot(κ,m):= 2[R(κ,m)+C E_ out]+2LW . Lemma 8 (Gradient bias). Under the conditions of Lemma 7 (which inherit Theorem 4’s parameter choices λ∗,Ms∗,T,δ⋆,δtraj,γT+1λ ,M_s ,T, _ , _ traj,γ^T+1) and the graph-tail assumption δ~:=(Δ−1)ρ<1 δ:=( -1)ρ<1, conditional on EM∩ErffE_M∩ E_ rff, ‖[^i(k)]−∇iJ((k))‖ E[ g_i^(k)]- _ θ_iJ( θ^(k)) (39) ≤GDκc(3ϵQ+2Rtot(κ,m))1−γ+ϵagg(κ), ≤ GD_ _c( 3\, _Q+ 2\,R_ tot(κ,m))1-γ+ _ agg(κ), with the aggregation-bias term ϵagg(κ):=Gc(1−γ)(1−δ~)⋅Δ−1δ~κc+1. aligned _ agg(κ):= Gc(1-γ)(1- δ)· -1 δ _c+1. aligned (40) When κπ=0 _π=0, the within-bin route in the proof vanishes by tower against σ(Xℓκ)σ(X_ ^κ) conditional on ℱkQF_k^Q (since ^ℓ(k) w_ ^(k) is fixed and the gradient sample is independent given (k) θ^(k)), and the constant 2LW∗2LW inside RtotR_ tot may be replaced by 0 as RtotR_ tot enters this bias bound and Lemma 9 (the L2L^2 bound of Lemma 7 retains it, since the fluctuation cancels only in score-weighted first moments); this step uses that the deployed critic is linear in ϕ~raw φ raw (no value clipping). Lemma 9 (Critic-conditional bias-squared). Define ϵb2:=supk,iQ^∥[^i(k)∣Q^,(k)]−∇iJ∥2 _b^2:= _k,iE_ Q E[ g_i^(k) Q, θ^(k)]- _ θ_iJ ^2. Under the conditions of Lemma 8, ϵb2 _b^2 ≤2ϵagg(κ)2 ≤ 2 _ agg(κ)^2 (41) +2G2Dκc2(6ϵQ2+4Rtot(κ,m)2)(1−γ)2. + 2G^2D_ _c^2(6 _Q^2+4R_ tot(κ,m)^2)(1-γ)^2. When κπ=0 _π=0, the bound holds with Rtot(κ,m)R_ tot(κ,m) replaced by 2[R(κ,m)+C′Eout] 2\,[R(κ,m)+C E_ out] (equivalently, 2LW∗→02LW → 0): conditioning on (Q^,(k))( Q, θ^(k)) fixes ^ℓ(k) w_ ^(k), the fluctuation cancels inside the conditional bias, νπ[(ℓ⊤^ℓ(k))∇ilogπi]=E_ν^π[( η_ w_ ^(k))\, _ θ_i _i]=0 for every fixed ^ℓ(k) w_ ^(k), and this cancellation occurs before any absolute values or Jensen step; the conditional-feature error is then bounded via Theorem 4 with the same failure budget (Appendix N). V-F Algorithm Algorithm 1 CDCPG with projected updates Input: i(0)⊆Θ0\ θ_i^(0)\ _0, κ, κc=κ+κπ _c=κ+ _π, m, λ, η, MsM_s, MgM_g, K, projection radius W∗W (Lemma 5). Preprocessing: for each i∈[n]i∈[n], sample (i,ℓ,bi,ℓ)ℓ=1m\( ω_i, ,b_i, )\_ =1^m independently. 1:for k=0,…,K−1k=0,…,K-1 do 2: Draw shared s(k),g(k)D_s^(k),D_g^(k) under π(k)π^(k). 3: for each i∈[n]i∈[n] in parallel do 4: Compute i(k),i(k)M_i^(k),b_i^(k) as in Definition 4. 5: Set ^i(k),raw←(i(k)+λ)−1i(k) w_i^(k), raw←(M_i^(k)+λI)^-1b_i^(k) if σmin(i(k)+λ)>0 _ (M_i^(k)+λI)>0, in implementation above a small numerical threshold, else 0. 6: Set ^i(k)←Π:‖≤W∗(^i(k),raw) w_i^(k)← _\w: w ≤ W \( w_i^(k), raw). 7: Set Q^i(k)()←ϕ~i,κraw()⊤^i(k) Q_i^(k)(z)← φ_i,κ raw(z) w_i^(k). 8: Gather ^ℓ(k)ℓ∈iκc\ w_ ^(k)\_ ∈N_i _c. 9: Compute ^i(k) g_i^(k) via (37). 10: i(k+1)←ΠΘ0,i(i(k)+η^i(k)) θ_i^(k+1)← _ _0,i( θ_i^(k)+η g_i^(k)). 11: end for 12:end for Output: (R) θ^(R) with R∼Unif0,…,K−1R \0,…,K-1\, so that the trajectory-average guarantees below bound n−1‖η((R))‖2n^-1E G_η( θ^(R)) ^2 directly; the final iterate (K) θ^(K) may be returned in practice. Per-agent computation is (Ms(mDκdS+m2)+m3+MgDκcmDκdS)O(M_s(mD_κd_S+m^2)+m^3+M_gD_ _cmD_κd_S), where the mDκdSmD_κd_S factors account for evaluating the random-feature maps at each sample; inter-agent algorithmic communication, excluding shared-oracle sample delivery, is (Dκcm)O(D_ _cm) scalars per iteration for weight exchange; sample delivery additionally contributes ((Ms+Mg)Dκc+κ+1(dS+dA))O((M_s+M_g)D_ _c+κ+1(d_S+d_A)) coordinates per agent per iteration, up to constant factors for current and successor tuples, after a one-time preprocessing dissemination of feature seeds (with a public master seed and si=Hash(i,master)s_i=Hash(i,master), no exchange is needed; otherwise each agent broadcasts one seed to its κc _c-neighborhood, so each agent receives (Dκc)O(D_ _c) seed words; explicit exchange of the maps would instead cost (mDκdS)O(mD_κd_S) scalars per neighbor pair). Under the shared-sample model (D1), each agent needs only the coordinates of the shared samples within its (κc+κ+1)( _c+κ+1)-neighborhood, that is, (Dκc+κ+1(dS+dA))O(D_ _c+κ+1(d_S+d_A)) scalars per sample, so the oracle admits a local-dissemination realization; with non-shared sampling, evaluating neighboring critics would additionally require coordinate exchange. Preprocessing stores (nm)O(nm) random-feature pairs, corresponding to (nmDκdS)O(nmD_κd_S) scalar frequency entries plus (nm)O(nm) phase entries. VI Convergence and Sample Complexity VI-A Main convergence bound Theorem 5 (Projected-gradient-mapping convergence). Under Sets A–D, with η≤1/(4LJ)η≤ 1/(4L_J), Algorithm 1 satisfies, conditional on EM∩ErffE_M∩ E_ rff, 1nK∑k=0K−1‖η((k))‖2 1nK _k=0^K-1E G_η( θ^(k)) ^2 ≤C1ΔJnηK+C2σg2Mg+C3ϵb2, ≤ C_1 _Jnη K+ C_2 _g^2M_g+C_3 _b^2, (42) for universal constants C1,C2,C3C_1,C_2,C_3, where σg2:=G2Dκc2(LW∗)2/(1−γ)2 _g^2:=G^2D_ _c^2(LW )^2/(1-γ)^2 (the per-sample gradient magnitude is bounded by GDκcLW∗/(1−γ)GD_ _cLW /(1-γ) under the projected linear critic) and ϵb2 _b^2 is as in Lemma 9. Corollary 1 (Step-size choice). With η=1/(4LJ)η=1/(4L_J), the right-hand side of (42) is (LJΔJnK)+(σg2Mg)+(ϵagg(κ)2)+(G2Dκc2(ϵQ2+Rtot2)(1−γ)2). aligned O\! ( L_J _JnK )+O\! ( _g^2M_g )+O( _ agg(κ)^2)+O\! ( G^2D_ _c^2( _Q^2+R_ tot^2)(1-γ)^2 ). aligned With ΔJ=(n) _J=O(n) (which suffices: ΔJ≤2nQmax _J≤ 2nQ_ ) and LJL_J assumed n-independent per (D2)–(D3) (Appendix B), the first term is (LJ/K)O(L_J/K), independent of n in its leading prefactor. VI-B Fixed-locality complexity In this regime κ and m are problem primitives. Define the structural floor ϵfloor(κ,m):=Cfloor[ _ floor(κ,m)=C_ floor [ ϵfloorbin+ϵfloortrunc(κ) _ floor bin+ _ floor trunc(κ) (43) +ϵfloorrff(m)+ϵfloorgraph(κ)], + _ floor rff(m)+ _ floor graph(κ) ], where ϵfloorbin:=G2Dκc2Cbintot 2/(1−γ)2,ϵfloortrunc(κ):=G2Dκc2[(1+C′)Etrunc(κ)]2/(1−γ)2,ϵfloorrff(m):=G2Dκc2[(1+C′)Erff(m)]2/(1−γ)2,ϵfloorgraph(κ):=ϵagg(κ)2, aligned _ floor bin&:=G^2D_ _c^2C_ bin tot\,2/(1-γ)^2,\\ _ floor trunc(κ)&:=G^2D_ _c^2[(1+C )E_ trunc(κ)]^2/(1-γ)^2,\\ _ floor rff(m)&:=G^2D_ _c^2[(1+C )E_ rff(m)]^2/(1-γ)^2,\\ _ floor graph(κ)&:= _ agg(κ)^2, aligned (44) with Cbintot:=2Cbin+2LW∗C_ bin tot:= 2C_ bin+2LW and CfloorC_ floor a universal constant. Theorem 6 (Sample complexity, uniform TD-stability). Under Sets A–D with κ,mκ,m fixed problem primitives such that m satisfies the RFF feasibility relation (13) of Theorem 1 at confidence δrff _ rff and accuracy ϵP(m,δrff,n) _P(m, _ rff,n), Δ≥2 ≥ 2, δ~=(Δ−1)ρ<1 δ=( -1)ρ<1, and δM+δrff<1 _M+ _ rff<1, there exists ϵ0>0 _0>0 depending on primitives such that for any ϵ∈(0,ϵ0]ε∈(0, _0], Algorithm 1 with parameters ϵQ=((1−γ)ϵ/(GDκc)),λ∗=0,Ms∗=~(L6W∗2G2Dκc2μM2(1−γ)2ϵ),Mg∗=(σg2/ϵ),K∗=(LJ/ϵ),η∗=1/(4LJ),δ⋆=δtraj=Θ(ϵQ2/(LW∗+Qmax)2), aligned _Q&=O((1-γ) ε/(GD_ _c)),\\ λ &=0,\\ M_s &= O\! ( L^6W 2G^2D_ _c^2 _M^2(1-γ)^2ε ),\\ M_g &=O( _g^2/ε),\\ K &=O(L_J/ε),\\ η &=1/(4L_J),\\ _ &= _ traj= ( _Q^2/(LW +Q_ )^2 ), aligned (45) satisfies the following guarantee. The truncation horizon is set to T=⌈log(1/δ⋆)/log(1/γ)⌉−1T= (1/ _ )/ (1/γ) -1, the smallest integer for which γT+1≤δ⋆γ^T+1≤ _ . With probability at least 1−δM−δrff1- _M- _ rff over the preprocessing random-feature draw, conditional on the resulting favorable events EM∩ErffE_M∩ E_ rff, the expectation over the subsequent algorithmic sampling randomness (s(k),g(k)k<K∗)(\D_s^(k),D_g^(k)\_k<K ) satisfies 1nK∗∑k‖η((k))‖2≤ϵ+ϵfloor(κ,m), aligned 1nK _kE G_η( θ^(k)) ^2≤ε+ _ floor(κ,m), aligned (46) where the per-iteration failure events (Elstdi,k)c(E_ lstd^i,k)^c and confinement-failure mass δtraj+γT+1 _ traj+γ^T+1 are absorbed into the ϵε-budget through the parameter choices above. A stronger high-probability guarantee over all algorithmic samples would require a separate failure-budget accounting over K∗,nK ,n and the LSTD, confinement, and gradient events. The shared-oracle complexity is Nglobal=K∗(Ms∗+Mg∗)=~(1/ϵ2). aligned N_ global=K (M_s +M_g )= O(1/ε^2). aligned (47) Each shared global sample is observed by every agent under the shared-sample oracle (D1), so NglobalN_ global also counts the number of local observations per agent under this oracle; the quantity ~(1/(nϵ2)) O(1/(nε^2)) is the same shared-oracle count amortized over the n agents as an accounting convention, not a physical per-agent trajectory count. Without shared samples, each agent’s local sampling cost would be counted separately. The prefactor depends polynomially on LJ,Dκ,Dκc,g~α,W∗,1/μM(m)L_J,D_κ,D_ _c, g_α,W ,1/ _M(m). The lower-bound comparison invoked for the ϵε-exponent is with the smooth nonconvex benchmark of [2], whose oracle, namely unbiased bounded-variance stochastic gradients without constraints, differs from the present shared generative model with a biased localized estimator and projected updates; the agreement claimed is therefore at the exponent level only. Explicitly, the cited bound is Ω(ϵg−4) ( _g^-4) for driving ‖∇F‖≤ϵg ∇ F ≤ _g, and becomes Ω(ϵ−2) (ε^-2) under the reparameterization ϵ=ϵg2ε= _g^2 matching the squared-stationarity convention here. Excess-to-floor reading. Theorem 6 bounds the averaged stationarity by ϵ+ϵfloor(κ,m)ε+ _ floor(κ,m) with ϵε the excess above the floor: for a total target τ with 0<τ−ϵfloor(κ,m)≤ϵ00<τ- _ floor(κ,m)≤ _0, invoking it with ϵ=τ−ϵfloor(κ,m)ε=τ- _ floor(κ,m) gives Nglobal=~((τ−ϵfloor(κ,m))−2)N_ global= O((τ- _ floor(κ,m))^-2), and the ~(τ−2) O(τ^-2) reading is valid exactly in the regime ϵfloor(κ,m)≤cτ _ floor(κ,m)≤ cτ for a fixed c<1c<1. The theorem is stated with the generic constant CbinC_ bin; Lemma 6 licenses the refined gap-dependent floor, with Cη(1+2γ)L2C_η(1+2γ)L^2 replaced by ‖i,κ‖ _i,κ θ , whenever the latter is smaller. The proof is in Appendix P. Remark 2 (Network-size scaling of the prefactor). Under fixed κ, Dκc≤CDΔκcD_ _c≤ C_D _c, with CDC_D an absolute constant of bounded-degree neighborhood growth, is bounded independently of n, and no explicit polynomial factor in n appears in the leading prefactor of NglobalN_ global provided that LJL_J, μM−1 _M^-1 (hence W∗W , C′C , CbinC_ bin), the feature-scale constant g~α g_α, and the preprocessing failure probabilities δM,δrff _M, _ rff are all uniform in n; the simultaneous RFF feasibility relation (13) retains a logarithmic dependence on n, and each shared oracle sample carries (n(dS+dA))O(n(d_S+d_A)) coordinates even though only local coordinates need be delivered per agent. Should any of these constants scale with n, for example LJL_J, whose descent factor K∗=(LJ/ϵ)K =O(L_J/ε) transmits the scaling to NglobalN_ global, or μM _M, which the union-bound discussion of Assumption Set C allows to deteriorate with n, the prefactor inherits that dependence. The cap Dκc≤nD_ _c≤ n becomes binding only when the realized neighborhood growth reaches the network size, i.e. when κc _c is of the order of the graph diameter; the crude envelope Δκc≥n _c≥ n does not by itself imply this (on a path graph Dκ=2κ+1D_κ=2κ+1 grows linearly while 2κ2^κ exceeds n already at κ=log2nκ= _2n). In that diameter-scale regime the prefactor carries an explicit factor of n2n^2 through Dκc2D_ _c^2. The polynomial degree in 1/μM1/ _M is at most 44 in the saturating regime through W∗2/μM2W 2/ _M^2. Moreover, under the present simultaneous union-bound RFF certificate, maintaining fixed approximation accuracy ϵP _P, fixed confidence δrff _ rff, and fixed local primitives as n grows requires m=Ω(logn)m= ( n) through (13); combined with Proposition 2, this gives μM−1=Ω(logn) _M^-1= ( n). Hence the present proof cannot maintain a fully n-uniform prefactor under these fixed-accuracy conditions, and at best polylogarithmic hidden n-dependence should be expected. Theorem 7 (Sample complexity, trajectory-conditional). Under Sets A, B, D, fix a threshold μtraj>0 _ traj>0 and evaluate all parameters and constants of Theorem 6 with μM _M replaced by μtraj _ traj throughout; the threshold enters statements (a)–(b) only through these constants, and Assumption 5 (at this μtraj _ traj) is invoked only in statements (c)–(d). Define the predictable per-iteration events Ak:=infi∈[n]σmin(i(k))≥μtraj,k=0,…,K∗−1, aligned A_k:= \ _i∈[n] _ (M_i θ^(k))≥ _ traj \, k=0,…,K -1, aligned (48) each ℱk−F_k^--measurable, and the trajectory event Etraj:=⋂k=0K∗−1AkE_ traj:= _k=0^K -1A_k. The following statements jointly characterize the guarantee: (a) (Mass-weighted stopped-process inequality; no (C′) premise.) The unconditional inequality [1nK∗∑k=0K∗−1‖η((k))‖2 1A0∩⋯∩Ak 1Erff]≤ϵ+ϵfloor(κ,m) aligned &E\! [\, 1nK \! _k=0^K -1 G_η( θ^(k)) ^2\,1_A_0∩·s∩ A_k\,1_E_ rff ]\\ & ≤ε+ _ floor(κ,m) aligned holds, the expectation being taken over the joint randomness of the random-feature preprocessing and the subsequent algorithmic sampling. Equivalently, writing τ:=infk:Akc∧K∗τ:= \k:A_k^c\ K for the first-failure stopping time and noting that A0∩⋯∩Ak=τ>k1_A_0∩·s∩ A_k=1_\τ>k\, [1nK∗∑k=0τ−1‖η((k))‖2 1Erff]≤ϵ+ϵfloor(κ,m). aligned E\! [\, 1nK \! _k=0^τ-1 G_η( θ^(k)) ^2\,1_E_ rff ]≤ε+ _ floor(κ,m). aligned (49) In particular, for the randomized output (R) θ^(R) of Algorithm 1 with R∼Unif0,…,K∗−1R \0,…,K -1\ drawn independently of the run, [n−1‖η((R))‖2 1R<τ 1Erff]E [n^-1 G_η( θ^(R)) ^2\,1_\R<τ\\,1_E_ rff ] is bounded by the same right-hand side. Because the average is normalized by K∗K rather than by the realized prefix length, statement (a) is vacuously satisfiable under early stopping (τ=0τ=0 zeroes the left side): it is a mass-weighted stopped-process inequality, not, by itself, a convergence guarantee. The convergence content is supplied by statements (c)–(d), which invoke Assumption 5 prospectively; the selective-output clause below inherits the same qualification. (b) (Global favorable-event bound.) Since Etraj⊆A0∩⋯∩AkE_ traj A_0∩·s∩ A_k for every k≤K∗−1k≤ K -1, statement (a) implies [1nK∗∑k=0K∗−1‖η((k))‖2 1Etraj∩Erff]≤ϵ+ϵfloor(κ,m). aligned E\! [\, 1nK \! _k=0^K -1 G_η( θ^(k)) ^2\,1_E_ traj∩ E_ rff ]≤ε+ _ floor(κ,m). aligned (50) (c) (Event probability.) ℙ(Etraj∩Erff)≥1−δMtraj−δrffP(E_ traj∩ E_ rff)≥ 1- _M traj- _ rff by Assumption 5 and the favorable RFF event. (d) (Conditional consequence.) If δMtraj+δrff≤1/2 _M traj+ _ rff≤ 1/2, dividing the bound of statement (b) by ℙ(Etraj∩Erff)≥1/2P(E_ traj∩ E_ rff)≥ 1/2 yields [1nK∗∑k=0K∗−1‖η((k))‖2|Etraj∩Erff]≤2(ϵ+ϵfloor(κ,m)). aligned &E\! [\, 1nK \! _k=0^K -1 G_η( θ^(k)) ^2\, |\,E_ traj∩ E_ rff ]\\ & ≤ 2 (ε+ _ floor(κ,m) ). aligned Statement (a) is the rigorous core of the result: each per-iteration descent inequality is multiplied by the predictable indicator A0∩⋯∩AkErff∈ℱk−1_A_0∩·s∩ A_k1_E_ rff∈F_k^- before expectations are taken, so that the concentration step never conditions on the global future event EtrajE_ traj, and the telescoped inequality coincides with the descent inequality summed over the stopped process (k)k<τ\ θ^(k)\_k<τ on ErffE_ rff. Statements (b) and (d) are derived consequences, the latter holding in the standard high-probability favorable-event regime. The shared-oracle complexity is Nglobaltraj=K∗(Ms∗+Mg∗)=~(LJL6W∗2G2Dκc2μtraj2(1−γ)2ϵ2+LJσg2ϵ2), aligned N_ global traj&=K (M_s +M_g )\\ &= O\! ( L_JL^6W 2G^2D_ _c^2 _ traj^2(1-γ)^2ε^2+ L_J _g^2ε^2 ), aligned with W∗W and all derived constants evaluated using μtraj _ traj in place of μM _M; the factor LJL_J in the first term enters through K∗=(LJ/ϵ)K =O(L_J/ε) multiplying Ms∗M_s . Per-iteration LSTD failure events (Elstdi,k)c(E_ lstd^i,k)^c and confinement failure mass δtraj+γT+1 _ traj+γ^T+1 are absorbed into the ϵε-budget by the parameter choices of Theorem 6 (with δ⋆ _ included). Proof. The proof, which combines predictable-event factorization with a stopped-process descent telescoping and keeps the RFF favorable event ErffE_ rff inside every per-step indicator, is deferred to Appendix Q. ∎ Proposition 3 (Diagnostic for (C′)). Set rM(Ms,δ):=CM(L2log(2nK(m+1)/δ)/Ms+L2log(2nK(m+1)/δ)/Ms)r_M(M_s,δ):=C_M (L^2 (2nK(m+1)/δ)/M_s+L^2 (2nK(m+1)/δ)/M_s ) (matrix Bernstein with the variance and linear terms; one may take CM=4C_M=4: with :=ϕ~raw(ϕ~raw−γϕ~raw)′⊤Y:= φ raw( φ raw-γ φ raw ) one has ‖≤(1+γ)L2≤2L2 Y ≤(1+γ)L^2≤ 2L^2, the centered summand obeys ‖≤4L2 X ≤ 4L^2 with max‖⊤‖,‖⊤‖≤4L4 \ EXX , EX X \≤ 4L^4, and rectangular matrix Bernstein, applied through the Hermitian dilation of dimension 2(m+1)2(m+1), yields 22L2ℓ/Ms+83L2ℓ/Ms2 2\,L^2 /M_s+ 83L^2 /M_s with ℓ=log(2nK(m+1)/δ) = (2nK(m+1)/δ) the dimension–union logarithm; both coefficients are dominated by CM=4C_M=4). Conditional on ℱk−F_k^-, the transition samples (,,′,′)(s,a,s ,a ) in s(k)D_s^(k) are i.i.d. from the joint one-step law dπ(k)⊗π(k)⊗ℙ⊗π(k)d _ θ^(k) _ θ^(k) P _ θ^(k), so matrix Bernstein applies conditionally and a union bound over i∈[n],k<Ki∈[n],k<K yields, with probability ≥1−δ≥ 1-δ, supi,k‖i(k)−i(k)‖≤rM(Ms,δ). aligned _i,k M_i^(k)-M_i θ^(k) ≤ r_M(M_s,δ). aligned (51) Consequently, the empirical test Tcert:=infi,kσmin(i(k))≥2rMT_ cert:=\ _i,k _ (M_i^(k))≥ 2r_M\ has false-certification probability at most δ: with probability at least 1−δ1-δ, whenever TcertT_ cert passes, the population lower bound infi,kσmin(i(k))≥rM _i,k _ (M_i θ^(k))≥ r_M also holds, equivalently ℙ(Tcert∩infi,kσmin(i(k))<rM)≤δ. aligned P (T_ cert∩\ _i,k _ (M_i θ^(k))<r_M\ )≤δ. aligned (52) Inequality (52) is a simultaneous false-certification bound: it controls the joint probability of certifying while the population condition fails. It does not by itself control the conditional probability ℙ(infi,kσmin(i(k))<rM|Tcert)P ( _i,k _ (M_i θ^(k))<r_M\, |\,T_ cert ), an ordinary frequentist conditional in which no prior is involved, which additionally requires a lower bound on the test-passing probability ℙ(Tcert)P(T_ cert): a test that never passes satisfies (52) vacuously. A less conservative certificate uses μ^cert:=infi,kσmin(i(k))−rM μ_ cert:= _i,k _ (M_i^(k))-r_M; whenever μ^cert>0 μ_ cert>0, the executed run satisfied infi,kσmin(i(k))≥μ^cert _i,k _ (M_i θ^(k))≥ μ_ cert except on an event of probability at most δ; this is a post-hoc lower-confidence statement about the realized trajectory. It does not retroactively instantiate the parameter choices of Theorem 7, which require a threshold fixed before the run. Either form is post-hoc: rMr_M depends on MsM_s, and the sample-complexity choice of MsM_s depends on 1/μtraj21/ _ traj^2, so pre-run application requires a pilot-budget iteration, which calibrates parameters but does not certify the main run. The constants W∗,C′,Cbin,Ms∗,ϵfloorW ,C ,C_ bin,M_s , _ floor in Theorem 7 are recomputed with μM _M replaced by μtraj _ traj throughout. The diagnostic proposition makes the empirical control of (C′) precise in the false-certification sense: σmin(i(k)) _ (M_i^(k)) is computed online from i(k)M_i^(k), and the test σmin(i(k))>2rM _ (M_i^(k))>2r_M carries simultaneous false-certification probability at most δ for the population lower bound via (52). Scope of certification. Proposition 3 controls only the population TD-stability event (C′); it does not by itself certify the vector-concentration events for i(k)−i(k)i∗b_i^(k)-M_i^(k)w_i used in Theorem 3, nor the confinement and gradient-sample events. Those events are absorbed in expectation through the bad-event budget of Theorem 7’s underlying parameter choices, exactly as in Theorem 6. When (C′) is taken as an assumption, Theorem 7 has failure probability δMtraj+δrff _M traj+ _ rff as stated. The certificate does not substitute for this assumption in statements (c)–(d): inequality (52) bounds a joint probability and supplies no lower bound on ℙ(Etraj)P(E_ traj), so the theorem’s failure budget cannot be obtained by replacing δMtraj _M traj with δ. Prospective use therefore requires (C′) (or a pre-run lower bound on μtraj _ traj) as a premise; the certificate provides post-hoc validation of the executed run, and statements (a)–(b), which need no probability premise, remain the unconditional core. Prospective versus post-hoc use. For a prospective sample-complexity guarantee, μtraj _ traj must be fixed before the algorithm runs, so that Ms∗,λ∗,W∗M_s ,λ ,W and the structural-floor constants are chosen consistently with that lower bound. A post-hoc certificate validates that the realized trajectory satisfied the chosen μtraj _ traj; it does not by itself retroactively determine the parameters. A pilot run, with a budget separate from the analyzed run, can calibrate the numerical scale of μtraj _ traj and MsM_s, but because the main run’s parameter sequence differs from the pilot’s, the pilot does not certify the main trajectory; prospective certification would require either a stability-on-a-tube argument (the continuity of ↦i θ M_i θ, Lemma 10, provides a route) or an online stopping rule, which we leave to future work. Remark 3 (Floor scaling). By the definitions, ϵfloortrunc(κ)∝[(1+C′)c~ρκ+1]2 _ floor trunc(κ) [(1+C ) cρ^κ+1]^2 and ϵfloorrff(m)∝[(1+C′)ϵP(m)]2 _ floor rff(m) [(1+C ) _P(m)]^2, with C′=(1+γ)L2/μMC =(1+γ)L^2/ _M and ϵP(m)2=~(g~α2DκdS/m) _P(m)^2= O( g_α^2D_κd_S/m) (using CRFF(d)=16(d+2)C_ RFF(d)=16(d+2) from the proof of Theorem 1); ϵfloorgraph(κ) _ floor graph(κ) decays as δ~2(κc+1) δ^2( _c+1). The within-bin floor ϵfloorbin∝(Cbintot)2 _ floor bin (C_ bin tot)^2 with Cbintot=2Cbin+2LW∗C_ bin tot= 2C_ bin+2LW contains two contributions: a matrix-perturbation term Cbin=Θ(L3U1/μM)C_ bin= (L^3U_1/ _M) (from Lemma 4, scaling with U1U_1) and a direct pointwise within-bin term 2LW∗2LW (from Lemma 7, scaling with W∗W ); Lemma 6 gives an exact matrix-gap form of the perturbation contribution that vanishes identically at full locality. The conditioning amplification is governed by μM(m) _M(m), which the present analysis does not pin down beyond the upper bound μM≤(m−1/2) _M≤O(m^-1/2) of Proposition 2, while the RFF component also retains its explicit finite-feature approximation factor ϵP(m)2 _P(m)^2. We therefore record the floor behavior under two explicitly hypothesized conditioning scenarios. A floor-level consequence of the obstruction. Since every admissible certificate obeys μM(m)≤(1+γ)L2/m+1 _M(m)≤(1+γ)L^2/ m+1 (Proposition 2), the generic constant satisfies, at every m, Cbin=Cη(1+2γ)L3U1μM≥Cη(1+2γ)1+γLU1m+1, aligned C_ bin= C_η(1+2γ)L^3U_1 _M\;≥\; C_η(1+2γ)1+γ\,L\,U_1 m+1, aligned (53) while 2LW∗2LW obeys only the upper envelope W∗=(1/μM)W =O(1/ _M) (no lower scaling is claimed for it; the generic CbinC_ bin component alone carries the certificate-level growth). Since L=r¯2+2L= r^2+2 and U1=1+2γg~αr¯/(1−γ)U_1=1+ 2γ g_α r/(1-γ) are m-independent by definition, the dimensional obstruction forces the certified generic within-bin term to grow at least linearly in m, in squared units and with the remaining primitive factors held fixed; μM=Θ(m−1/2) _M= (m^-1/2) is the best-case conditioning scaling, not merely one scenario. This is a statement about the certificate produced by the present upper-bound analysis, not a lower bound on the actual algorithmic error; the refined exact-gap form (Lemma 6), which replaces Cη(1+2γ)L2C_η(1+2γ)L^2 by ‖i,κ‖ _i,κ θ , avoids this conclusion whenever the gap vanishes or decays sufficiently; the gap vanishes identically at full locality. Scenario 1 (m fixed; μM(m) _M(m) a fixed primitive). If the random-feature dimension m is fixed as a problem primitive, rather than sent to infinity, and the assumed or diagnosed lower bound μM(m) _M(m) is treated as the fixed conditioning constant for that chosen m, then C′,W∗,U1C ,W ,U_1 are (1)O(1) relative to the stationarity tolerance ϵε, the RFF floor is the fixed quantity ϵfloorrff(m)=~(g~α2DκdS/m) _ floor rff(m)= O( g_α^2D_κd_S/m), ϵfloortrunc(κ) _ floor trunc(κ) decays as ρ2(κ+1)ρ^2(κ+1) in κ, and the within-bin floor is bounded. Even at fixed m, however, the certificate-level bound above applies at that m (Cbin≳LU1m+1C_ bin LU_1 m+1); bounded here means bounded as ϵ→0ε→ 0 at the chosen m, not numerically small. Scenario 2 (saturating μM≍m−1/2 _M m^-1/2). The dimensional obstruction (Proposition 2) is an upper bound, μM(m)≤(m−1/2) _M(m)≤O(m^-1/2): it excludes asymptotically slower decay (such as m−1/4m^-1/4) and permits faster deterioration (such as m−1m^-1). In the saturating-conditioning scenario in which the obstruction upper bound is order-tight, i.e. μM=Θ(m−1/2) _M= (m^-1/2), with the remaining primitive factors (including U1U_1) held Θ(1) (1), one has (1+C′)2=Θ(m)(1+C )^2= (m), Cbin2=Θ(m)C_ bin^2= (m), and W∗2=(m)W 2=O(m). Then: • The proved RFF certificate satisfies only ϵfloorrff(m)=~(1) _ floor rff(m)= O(1) (an upper envelope: Θ(m)⋅~(1/m) (m)· O(1/m)); no matching lower rate is claimed. • Cbin=Θ(m)C_ bin= ( m) and 2LW∗=(m)2LW =O( m); thus (Cbintot)2=Θ(m)(C_ bin tot)^2= (m) and the generic within-bin certificate is ϵfloorbin=Θ(m) _ floor bin= (m). A more pessimistic conditioning hypothesis. If, for a particular model class, the available certificate is additionally known to satisfy μMcert=Θ(1/m) _M cert= (1/m), and the analysis substitutes that certificate for μM _M, then (1+C′)2=Θ(m2)(1+C )^2= (m^2) and W∗=(m)W =O(m), giving ϵfloorbin=Θ(m2) _ floor bin= (m^2) and ϵfloorrff=~(m) _ floor rff= O(m). The trace cap of Lemma 3 supplies only the (1/m)O(1/m) upper limitation on that certificate, and the certificate may be smaller or vanish, so the Θ(1/m) (1/m) premise is an additional hypothesis, not a consequence of the cap. This is a property of that certificate or problem class, not a general consequence of Lemma 3: the true σmin(i) _ (M_i θ) may be considerably larger than the certificate, and the only proved general upper bound on the true conditioning remains the (m−1/2)O(m^-1/2) of Proposition 2. Under the generic within-bin envelope in each scenario above, increasing m inflates the certified within-bin component, while the proved envelope for ϵfloorrff _ floor rff does not shrink beyond the rates stated above. The dimensional obstruction proves only the upper bound μM≤(m−1/2) _M≤O(m^-1/2); a corresponding tight lower-bound example would convert the saturating scenario into an unavoidable obstruction. We therefore treat m as a problem primitive rather than asserting an inevitable floor inflation. Corollary 2 (Specialized within-bin floor at κπ=0 _π=0). If κπ=0 _π=0, then in the proof of Lemma 8 the raw/conditional decomposition Q^ℓ(k)−Qℓπ=(⟨ϕ~ℓ,κπ,^ℓ(k)⟩−Qℓπ)+ℓ⊤^ℓ(k) Q_ ^(k)-Q_ ^π= ( φ_ ,κ^π, w_ ^(k) -Q_ ^π )+ η_ w_ ^(k) is performed before any application of Jensen or Cauchy–Schwarz, and the score-weighted expectation of the fluctuation term vanishes, [ℓ⊤^ℓ(k)∇ilogπi∣ℱkQ]=E[ η_ w_ ^(k)\, _ θ_i _i F_k^Q]=0, by tower against σ(Xℓκ)σ(X_ ^κ): the score is σ(Xℓκ)σ(X_ ^κ)-measurable when κπ=0 _π=0, ^ℓ(k) w_ ^(k) is ℱkQF_k^Q-measurable, the gradient sample is independent given (k) θ^(k), and the deployed critic is linear in ϕ~raw φ raw. Only the conditional-feature error is then routed through the critic bound, so CbintotC_ bin tot in ϵfloorbin _ floor bin may be replaced by 2Cbin 2\,C_ bin, and the saturating-conditioning inflation of Remark 3 continues to apply only through the matrix-perturbation contribution Cbin=Θ(L3U1/μM)C_ bin= (L^3U_1/ _M); the squared-bias version of this substitution is the κπ=0 _π=0 clause of Lemma 9, proved by cancelling inside the conditional bias before absolute values. The simulation results in Section VII operate in this regime. VI-C Adaptive-locality diagnostic Proposition 4 (Adaptive locality diagnostic). Under the conditions of Theorem 6 with m fixed and the strictly stronger hypothesis Δρ<1 ρ<1, suppose further that (i) m satisfies the RFF feasibility relation (13) at the selected radius κ∗κ , in the full form (13); the simplified ratio condition g~α(κ∗)2Dκ∗dS/m≤1 g_α(κ )^2D_κ d_S/m≤ 1 is a necessary scale, not a restatement of that relation; (i) the deterministic Set-C thresholds admit the uniform lower envelope μM(m,κ)≥μ¯M(m)>0 _M(m,κ)≥ μ_M(m)>0 over the working range [[0,κmax]][\![0, _ ]\!]; only the selected-radius event is realized after the single feature draw. This envelope makes the implicit fixed-point definition of κ∗κ below well-posed. Here κmax∈ℕ _ ∈N is a fixed working-range bound; features are drawn once, at the selected radius κ∗κ , after κ∗κ has been determined from the (oracle) decay constants, so (i) is a deterministic lower bound on the population constant μM(m,κ) _M(m,κ) across the range, not a probabilistic event over multiple feature draws. With the graph-growth constant CDC_D of Remark 2, so that Dκc≤CDΔκ+κπD_ _c≤ C_D ^κ+ _π (capped at n), define the constants Cg:=G2CD2Δ2κπc2((1−γ)(1−δ~))2,Ct(κ):=G2CD2Δ2κπ((1+C′(κ))(1+2/(1−γ)))2(1−γ)2, aligned C_g&:= G^2C_D^2 ^2 _πc^2((1-γ)(1- δ))^2,\\ C_t(κ)&:= G^2C_D^2 ^2 _π((1+C (κ))(1+2/(1-γ)))^2(1-γ)^2, aligned (54) where CgC_g is κ-independent and Ct(κ)=Ct(μM(m,κ))C_t(κ)=C_t( _M(m,κ)) inherits κ-dependence through C′(κ)=(1+γ)L2/μM(m,κ)C (κ)=(1+γ)L^2/ _M(m,κ). The radius κ∗κ is then defined implicitly as any positive integer in [[1,κmax]][\![1, _ ]\!] satisfying both κ∗≥log(CgCfloor/ϵ)2log(1/Δρ),κ∗≥log(Ct(κ∗)c~2Cfloor/ϵ)2log(1/Δρ); aligned κ &≥ (C_g\,C_ floor/ε)2 (1/ ρ),\\ κ &≥ (C_t(κ ) c^2\,C_ floor/ε)2 (1/ ρ); aligned (55) under hypothesis (i), the right-hand side of the second inequality is bounded by log(Ct(μ¯M(m))c~2Cfloor/ϵ)/(2log(1/Δρ)) (C_t( μ_M(m)) c^2\,C_ floor/ε)/(2 (1/ ρ)), so the fixed point exists provided this value lies in [[1,κmax]][\![1, _ ]\!]. A conservative explicit alternative replaces Ct(κ∗)C_t(κ ) by C¯t:=sup0≤r≤κmaxCt(r) C_t:= _0≤ r≤ _ C_t(r), finite under hypothesis (i), after which κ∗=⌈maxlog(CgCfloor/ϵ),log(C¯tc~2Cfloor/ϵ)/(2log(1/Δρ))⌉κ = \ (C_g\,C_ floor/ε), ( C_t c^2\,C_ floor/ε)\/(2 (1/ ρ)) is explicit. With κ∗κ so chosen, ϵfloortrunc(κ∗)≤ϵ/Cfloor _ floor trunc(κ )≤ε/C_ floor and ϵfloorgraph(κ∗)≤ϵ/Cfloor _ floor graph(κ )≤ε/C_ floor, and [1nK∗∑k‖η((k))‖2|EM∩Erff]≤3ϵ+Cfloor[ϵfloorbin(κ∗;m)+ϵfloorrff(m;κ∗)], aligned &E\! [\, 1nK _k G_η( θ^(k)) ^2\, |\,E_M∩ E_ rff ]\\ & ≤ 3ε+C_ floor [ _ floor bin(κ ;m)+ _ floor rff(m;κ ) ], aligned where, with κc∗:=κ∗+κπ _c :=κ + _π, ϵfloorrff(m;κ∗)=~(G2γ2r¯2(1−γ)4Dκc∗2(1+C′(κ∗))2CRFF(Dκ∗dS)g~α(κ∗)2m), aligned & _ floor rff(m;κ )\\ &\;= O\! ( G^2γ^2 r^2(1-γ)^4\,D_ _c ^2(1+C (κ ))^2C_ RFF(D_κ d_S)\, g_α(κ )^2m ), aligned an upper bound obtained from ϵfloorrff=G2Dκc2[(1+C′)Erff(m)]2/(1−γ)2 _ floor rff=G^2D_ _c^2[(1+C )E_ rff(m)]^2/(1-γ)^2 with Erff(m)=γr¯ϵP(m)/(1−γ)E_ rff(m)=γ r _P(m)/(1-γ) and ϵP(m)2=~(CRFF(Dκ∗dS)g~α2/m) _P(m)^2= O(C_ RFF(D_κ d_S) g_α^2/m) (no matching lower inversion is claimed; suppressing only fixed primitive factors, this is ~(Dκc∗2(1+μM(m,κ∗)−1)2g~α(κ∗)2Dκ∗dS/m) O(D_ _c ^2(1+ _M(m,κ )^-1)^2 g_α(κ )^2D_κ d_S/m)), and, exactly as in (43), ϵfloorbin(κ∗;m)=G2Dκc∗2(1−γ)2Cbintot(κ∗,m)2, aligned _ floor bin(κ ;m)= G^2D_ _c ^2(1-γ)^2\,C_ bin tot(κ ,m)^2, aligned (56) with Cbintot=2Cbin+2LW∗C_ bin tot= 2\,C_ bin+2LW (at κπ=0 _π=0, Corollary 2 replaces CbintotC_ bin tot by 2Cbin 2\,C_ bin). Neither component is a universal constant times its amplification factor: the κ∗κ -dependent prefactor Dκc∗2D_ _c ^2 is nonconstant, contributing at most a polylogarithmic factor in 1/ϵ1/ε on linear-growth graphs, leaving the quasi-polynomial classification unchanged under polynomial growth, and contributing a polynomial factor dominated by the stretched-exponential envelope under exponential growth. Since g~α(κ)=exp((DκdS)) g_α(κ)= (O(D_κd_S)) by its definition (it can grow exponentially in DκdSD_κd_S when 2πσ2>α22πσ^2>α^2, and the following are upper inflation envelopes) and κ∗=(log(1/ϵ))κ =O( (1/ε)), the surviving-floor inflation is governed by the neighborhood growth v(κ):=Dκv(κ):=D_κ: for linear growth (v(κ)=(κ)v(κ)=O(κ), e.g. path graphs, Dκ=2κ+1D_κ=2κ+1) the envelope is exp((log(1/ϵ))) (O( (1/ε))), i.e. polynomial in 1/ϵ1/ε; for polynomial growth v(κ)=(κp)v(κ)=O(κ^p), p>1p>1, it is quasi-polynomial, exp((logp(1/ϵ))) (O( ^p(1/ε))); and under exponential neighborhood growth v(κ)=(Δκ)v(κ)=O( ^κ) it is of stretched-exponential type, exp(((1/ϵ)c)) (O((1/ε)^c)) for a constant c>0c>0. In every case the inflation can violate (i) if m is held fixed. This proposition is an oracle bias-balancing diagnostic, not a rate improvement; it operates only in the regime where (i)–(i) remain valid at the selected κ∗κ . When the realized growth Dκc∗D_ _c reaches n (i.e. κc∗ _c of the order of the graph diameter), the cap Dκc∗≤nD_ _c ≤ n contributes an explicit factor of n2n^2 through Dκc∗2D_ _c ^2 in the surviving floor, consistent with Remark 2. The proof is in Appendix R. True ϵε-stationarity requires the floor itself at most ϵε; a sufficient condition, explicit up to the universal proof constant CfloorC_ floor, is Cbintot≤1−γGDκcϵ/(4Cfloor)C_ bin tot≤ 1-γGD_ _c ε/(4C_ floor), (1+C′)Erff(m)≤1−γGDκcϵ/(4Cfloor)(1+C )E_ rff(m)≤ 1-γGD_ _c ε/(4C_ floor), (1+C′)Etrunc(κ)≤1−γGDκcϵ/(4Cfloor)(1+C )E_ trunc(κ)≤ 1-γGD_ _c ε/(4C_ floor), and ϵagg(κ)≤ϵ/(4Cfloor) _ agg(κ)≤ ε/(4C_ floor). The binding constraint in practice is ϵfloorbin _ floor bin via W∗/μMW / _M. For a total stationarity target τ, the allocation is 3ϵopt+Cfloor[ϵfloorbin+ϵfloorrff]≤τ3 _ opt+C_ floor[ _ floor bin+ _ floor rff]≤τ; for example, ϵopt=τ/6 _ opt=τ/6 with the surviving floor at most τ/2τ/2. VII Numerical Experiments We evaluate CDCPG on a Linear-Coupled-Quadratic (LCQ) benchmark, a structured networked-control stress test with a closed-form linear–quadratic-regulator (LQR) reference. Each of n=9n=9 agents on a path graph carries scalar state i∈ℝs_i∈R and action i∈[−A,A]a_i∈[-A,A], with local dynamics it+1=ρdynit+βit+κdyn∑j∈i∖i(jt−it)+it, aligned s_i^t+1= _ dyns_i^t+βa_i^t+ _ dyn\! _j∈N_i \i\\!(s_j^t-s_i^t)+ _i^t, aligned (57) it∼(0,σd2) _i^t N(0, _d^2), and quadratic neighbor-coupled rewards ri=−i2−λn∑j∈i∖ij2−λai2r_i=-s_i^2- _n _j∈N_i \i\s_j^2- _aa_i^2. Parameters are listed in Table I; state and action are projected onto [−Smax,Smax][-S_ ,S_ ] and [−A,A][-A,A] as a numerical safeguard. Let LQRK_ LQR denote the gain solving the unconstrained discounted Riccati equation; because the implemented simulator clips states and actions, LQRK_ LQR is used as a reference controller and is not claimed to be optimal for the clipped MDP. The per-agent expected discounted return under the stochastic reference policy =−LQR+(,σπ2)a=-K_ LQRs+N(0, _π^2I) is Vσref=−2.713V_σ ref=-2.713 (verified by 5×1035× 10^3-episode Monte-Carlo). The averaged diagonal entry of LQRK_ LQR is K¯LQR=0.350 K_ LQR=0.350. The LCQ benchmark is not a literal instance of Sets A–D: linear dynamics and quadratic rewards are unbounded before clipping. The experiment serves as a structured regime-consistency check on the locality and finite-sample predictions, not a direct verification of the theorem assumptions. TABLE I: Parameters of the LCQ benchmark. ρdyn=0.7 _ dyn=0.7 β=0.5β=0.5 σd=0.10 _d=0.10 κdyn=0.20 _ dyn=0.20 λn=0.5 _n=0.5 λa=0.5 _a=0.5 A=5.0A=5.0 Smax=3.0S_ =3.0 σ0=0.5 _0=0.5 σπ=0.30 _π=0.30 γ=0.95γ=0.95 n=9n=9 VII-A Setup and baselines CDCPG is instantiated with κ=1,κπ=0,λ=10−4,η=5×10−2κ=1, _π=0,λ=10^-4,η=5× 10^-2 (cosine decay), Ms=2000,Mg=1024M_s=2000,M_g=1024. The zero-radius actor matches the actor-locality regime of Corollary 2; the corollary’s exact raw-feature fluctuation cancellation applies to the analyzed linear RFF critic and is not invoked for the structured quadratic critic used in this comparison. The main comparison uses a structured quadratic-basis state-value critic tailored to the LQR structure of the benchmark and should be viewed as an implementation-level demonstration of the locality predictions, not a direct verification of the theorem assumptions (which analyze the augmented RFF–LSTD critic of Definition 3). The separate rate-validation experiment in Section VII.C uses the augmented RFF–LSTD critic directly and isolates the critic-approximation behavior predicted by Theorem 1. Baselines: independent policy gradient (IPG); Networked Actor–Critic (Networked AC) [33] with one-hop consensus; multi-actor attention-critic (MAAC) [14]; and centralized policy gradient with a global linear Gaussian policy. All methods share the exploration scale σπ _π, per-iteration sample budget, and learning-rate schedule. All runs use K=200K=200 outer iterations and 55 random seeds; curves report the mean ± one standard deviation across seeds, the Riccati reference VσrefV_σ ref is verified by an independent 5×1035× 10^3-episode Monte-Carlo evaluation, and the conditioning proxy below is logged at every (i,k)(i,k) pair throughout training. The conditioning proxy σmin(i(k)) _ (M_i^(k)) is logged at every iteration with empirical median μ^M=0.41±0.05 μ_M=0.41± 0.05 across (i,k)(i,k); the median is reported as a summary statistic only; the certificate of Proposition 3 would report infi,kσmin(i(k)) _i,k _ (M_i^(k)) net of the concentration radius rMr_M, which these runs did not archive. This is the empirical singular-value scale of the implemented structured critic only; it neither certifies (C′) nor estimates the population conditioning of the analyzed RFF critic. The implementation value λ=10−4λ=10^-4 sits far below this scale; the observation is descriptive and is not a certification of the population side condition λ≤μM/4λ≤ _M/4 of Remark 1. VII-B Comparison with decentralized baselines Figures 1–3 and Table I report the comparison. CDCPG and Centralized close the gap to within 0.55%0.55\% of VσrefV_σ ref and are numerically close with 55 random seeds; we do not claim statistical indistinguishability at this seed count. Local-policy baselines plateau at 1.61.6–5.5%5.5\% gap. CDCPG uses a κπ=0 _π=0 actor (local policy) coupled with a κ=1κ=1 neighbor-aware critic; the advantage over IPG is thus consistent with the credit-assignment information carried by the critic’s policy-gradient signal (cf. Lemma 8, which propagates value information across the κc _c-neighborhood), not from a richer policy class. The Networked AC and MAAC baselines have similar policy-class structure but use consensus- or attention-aggregated value rather than the spectral conditional-expectation truncation analyzed here; their plateau is consistent with value-aggregation bias being one possible limiting factor, although this experiment does not isolate that mechanism from other implementation differences. Define k0.9:=mink:J¯k−J¯0≥0.9(Vσref−J¯0)k_0.9:= \k: J_k- J_0≥ 0.9(V_σ ref- J_0)\, the first iteration attaining 90%90\% of the reference improvement. CDCPG reaches the k0.9k_0.9 threshold in 1313 iterations versus 2525 for Centralized and 5555–133133 for the local baselines; this is a descriptive iteration-count result, and no causal variance-reduction claim is made. Figure 1: Per-agent discounted return J¯(k) J( θ_k) versus iteration k on LCQ (n=9n=9, 55 seeds, mean ± one std). Dashed reference Vσref=−2.713V_σ ref=-2.713. CDCPG matches the Centralized full-information baseline within 0.110.11 percentage points at 55 seeds. The comparison uses the structured quadratic-basis critic of Section VII-A; the analyzed RFF–LSTD critic is exercised in Fig. 4. Figure 2: Trajectory of the agent-0 diagonal policy weight on LCQ under each method; the dashed line is the network-average diagonal entry of the unconstrained Riccati gain, −K¯LQR=−0.350- K_ LQR=-0.350, a reference value rather than the exact agent-0 gain or the optimizer over the diagonal-policy class. CDCPG with the structured critic drives the diagonal entry of its κπ=0 _π=0 local feedback to the diagonal of LQRK_ LQR; the off-diagonal entries of LQRK_ LQR are not representable in this policy class, so the comparison object is the best diagonal local feedback rather than the global LQR controller. Figure 3: Final-iteration per-agent return on LCQ, mean ± one std over 55 seeds. Dashed reference: VσrefV_σ ref. TABLE I: LCQ benchmark, n=9n=9 path graph, K=200K=200, 55 seeds, σπ=0.30 _π=0.30. Final per-agent return J¯ J (mean and std), diagonal policy gain, signed gap to Vσref=−2.713V_σ ref=-2.713, and median iteration k0.9k_0.9 to reach 90%90\% of available improvement. The CDCPG row uses the structured quadratic-basis critic; the augmented RFF–LSTD critic of Definition 3 is exercised separately in Section VII.C. Method J¯ J (± std) Diag. gain Gap k0.9k_0.9 CDCPG with the structured critic −2.728(0.018)-2.728\,(0.018) −0.345-0.345 −0.55%-0.55\% 1313 Centralized −2.725(0.015)-2.725\,(0.015) −0.348-0.348 −0.44%-0.44\% 2525 Networked AC −2.756(0.042)-2.756\,(0.042) −0.252-0.252 −1.59%-1.59\% 5555 MAAC −2.852(0.029)-2.852\,(0.029) −0.135-0.135 −5.12%-5.12\% 113113 IPG −2.863(0.025)-2.863\,(0.025) −0.158-0.158 −5.53%-5.53\% 133133 In sample efficiency, CDCPG reaches the k0.9k_0.9 threshold in roughly half the iterations of Centralized and in a small fraction of those of the local baselines; these are observed iteration-count ratios at the present seed count, not claimed asymptotic speed-up factors. VII-C Feature-dimension trend We fit the augmented RFF critic of Definition 3 at varying m∈50,100,250,500,1000,2000m∈\50,100,250,500,1000,2000\ with κ and policy held fixed; the closed-form QσrefQ ref_σ provides the analytic unconstrained-LQ reference. Figure 4 reports the relative critic error |Q^−Qσref|/|Qσref| | Q-Q ref_σ |/ |Q ref_σ | averaged over 10410^4 test samples from dπd^π. The log-log fit yields slope −0.46-0.46 (R2=0.98R^2=0.98). The observed trend is compatible with the ~(1/m) O(1/ m) kernel-L1L^1 behavior of Theorem 1, but a direct finite-sample verification would require holding the conditioning σmin(i(k)) _ (M_i^(k)) fixed across m (it drifts with m; Remark 3) and measuring kernel-L1L^1 error rather than relative Q-error (a norm-ratio metric ‖Q^−Qσref‖L2/‖Qσref‖L2 Q-Q ref_σ _L^2/ Q ref_σ _L^2 would additionally avoid instability of pointwise ratios near zeros of QσrefQ ref_σ and is noted for future reporting); the measured error additionally carries truncation error and any mismatch between the clipped simulator and the analytic unconstrained-LQ reference; the error drops from 42%42\% at m=50m=50 to 7%7\% at m=2000m=2000. Figure 4: Relative Q-function approximation error |Q^−Qσref|/|Qσref| | Q-Q ref_σ |/ |Q ref_σ | versus RFF dimension m on LCQ (Ms=2000M_s=2000, 55 seeds, log-log axes). Fitted slope −0.46-0.46 (R2=0.98R^2=0.98). VII-D Decay proxy and ablations Figure 5 regresses log|Cov(ri,rj)| |Cov(r_i,r_j) | against graph distance; the fitted geometric rate is ρ^=0.86 ρ=0.86. With Δ=2 =2, δ~=(Δ−1)ρ^=0.86<1 δ=( -1) ρ=0.86<1 is compatible with the fixed-locality regime of Theorem 6; reward-covariance decay is a proxy, neither necessary nor sufficient, and does not certify Assumption 2(B2), which is a Q-function sensitivity condition. The stronger contraction Δρ^=1.72≮1 ρ=1.72 <1 required in Proposition 4 is not certified. Figure 5: Empirical absolute cross-agent reward covariance |Cov(ri,rj)| |Cov(r_i,r_j) | versus graph distance on LCQ (55 seeds, semi-log axes). Fitted geometric rate ρ^=0.86 ρ=0.86. Figure 6 and Table IV sweep κ (Theorem 4) and λ (Theorem 3) at K=150K=150, 33 seeds. The truncation sweep shows monotone gap reduction with consecutive-hop ratios ≈0.5≈ 0.5, consistent with Lemma 2; the κ=0κ=0 point is included as an empirical local-only baseline and lies outside the theorem condition κ≥max1,κπ+1κ≥ \1, _π+1\ for one-hop coupled rewards. The λ sweep is flat over λ∈10−6,10−4,10−2λ∈\10^-6,10^-4,10^-2\ (gaps −0.70%,−0.63%,−0.55%-0.70\%,-0.63\%,-0.55\%) and breaks at λ=1λ=1 (gap −9.77%-9.77\%), consistent with the side-condition scale μ^M/4≈0.10 μ_M/4≈ 0.10 implied by the median conditioning proxy (Section VII-A) and with Remark 1. (a) Truncation radius κ. (b) Regularization λ. Figure 6: CDCPG ablation on LCQ (K=150K=150, 33 seeds; mean ± one std). Dashed reference: Vσref=−2.713V_σ ref=-2.713. (a) Truncation-radius sweep with consecutive-hop ratios ≈0.5≈ 0.5, consistent with Lemma 2. (b) Regularization sweep with flat regime over four decades and break at λ=1λ=1, consistent with the side-condition scale μ^M/4 μ_M/4 at the median conditioning proxy μ^M≈0.41 μ_M≈ 0.41. TABLE IV: CDCPG ablation on LCQ (K=150K=150, 33 seeds). Final per-agent return J¯ J (mean and std) and signed gap to VσrefV_σ ref. Each sweep varies one parameter with the other held fixed: the κ sweep fixes λ=10−4λ=10^-4, and the λ sweep fixes κ=3κ=3. Sweep Setting J¯ J (± std) Gap κ 0 −2.852(0.040)-2.852\,(0.040) −5.13%-5.13\% 11 −2.778(0.030)-2.778\,(0.030) −2.40%-2.40\% 22 −2.748(0.025)-2.748\,(0.025) −1.29%-1.29\% 33 −2.732(0.028)-2.732\,(0.028) −0.70%-0.70\% λ 10−610^-6 −2.732(0.018)-2.732\,(0.018) −0.70%-0.70\% 10−410^-4 −2.730(0.018)-2.730\,(0.018) −0.63%-0.63\% 10−210^-2 −2.728(0.018)-2.728\,(0.018) −0.55%-0.55\% 11 −2.978(0.034)-2.978\,(0.034) −9.77%-9.77\% VII-E Summary of empirical evidence The four studies exercise complementary components of the theory. The baseline comparison (Figs. 1–3, Table I) probes the locality predictions: a κπ=0 _π=0 actor coupled with a κ=1κ=1 neighbor-aware critic recovers centralized performance on a benchmark whose interactions are genuinely networked. The m-sweep (Fig. 4) probes the feature-approximation component, with a fitted exponent compatible with Theorem 1 under the stated confounds. The covariance regression (Fig. 5) probes the plausibility of the decay regime, explicitly as a proxy. The λ-ablation (Fig. 6) probes the regularization analysis of Remark 1 and Theorem 4. None of these studies certifies an assumption; each is a consistency check against the specific mechanism the corresponding theorem isolates. Assumption-level certification via Proposition 3 and an end-to-end CDCPG row with the analyzed RFF–LSTD critic are the natural next experiments and lie outside the present study. VIII Conclusion We have refined spectral localized policy-gradient analysis for continuous networked MDPs in four structural directions: conditional-expectation Q-truncation that avoids the continuation-kernel mismatch of naive Bellman truncation; a feature-dimension-aware TD-stability hypothesis, reducible by an unconditional excitation bound to a symmetric persistence-of-excitation condition, with a trajectory-conditional companion theorem proved via predictable-event factorization and a predictable-prefix, equivalently stopped-process, bound that implies the corresponding global favorable-event bound; an explicit four-component structural floor whose certified within-bin penalty grows at least linearly in m under the generic envelope; this is an upper-bound artifact of the present raw-feature LSTD certificate, with saturating conditioning (μM≍m−1/2 _M m^-1/2) the best case, with a specialized reduction at κπ=0 _π=0; and an adaptive-locality bias-balancing diagnostic that selects the radius κ∗(ϵ)κ (ε) at which truncation and graph-decay residuals fall below ϵε. The matrix-Bernstein diagnostic bounds the simultaneous false-certification probability by δ for the population TD-stability component along realized iterates; it is a post-hoc certificate for the executed run rather than a prospective guarantee, and pilot runs serve only to calibrate parameters. Above the structural floor, the ϵε-dependence of the optimization and statistical terms in the fixed-(κ,m)(κ,m) shared-oracle complexity ~(1/ϵ2) O(1/ε^2) matches, at the exponent level, the standard smooth nonconvex stochastic-optimization lower bound under a different oracle model; the adaptive-locality result is a diagnostic, not a rate improvement. Open questions include feature constructions suppressing the within-bin penalty, lower-bound examples for the within-bin term; such an example would convert the saturating-conditioning regime from an upper-bound artifact into a proved obstruction, concrete policy-class conditions implying the trajectory-conditional hypothesis and the differentiated-decay regularity (D3), a fully worked coupled continuous model class verifying (A), (B2), the excitation bound of Lemma 3, and (D3) simultaneously, and extensions to independent-trajectory sampling. Appendix A Heuristic contraction route toward (B2) and (D3) We give a heuristic contraction route toward regimes in which Assumption (B2) and the differentiated-decay part of (D3) are expected to hold; both are taken as standing primitives in the main analysis, and the following is intended only as intuition for when they are expected to hold. A fully rigorous proof requires a distance-indexed influence-cone recursion and is omitted. Define Dunc:=2(Bf+σdS)D_ unc:=2(B_f+σ d_S) and L~f:=LfD11+Lπ2Dκπ L_f:=L_f D_1 1+L_π^2D_ _π, L~r L_r analogously. Sufficient-condition sketch for (B2). Under (A1)–(A3), if L~f<1 L_f<1, then (B2) is expected to hold with ρ=γ1/(κπ+1)ρ=γ^1/( _π+1) and a constant c depending on L~r,Dunc,γ L_r,D_ unc,γ. Sketch of argument. Couple two trajectories with synchronous Gaussian noise and the optimal W2W_2 coupling of actions. A distance-indexed influence recursion shows that discrepancies outside iκN_i^κ at time 0 propagate inward at unit rate per step under the bounded-Lipschitz dynamics. Rewards at i agree until the front reaches i1N_i^1, after which the residual is bounded by L~rDuncL~ft L_rD_ unc L_f^t in expectation. Summing with discount γtγ^t and front-propagation index τ∗=⌊(κ−κπ−1)/(κπ+1)⌋τ = (κ- _π-1)/( _π+1) yields (B2). A fully rigorous version requires a distance-indexed envelope er(t)=supd(i,j)≤r‖j−j′‖2e_r(t)= _d(i,j)≤ r E s_j-s_j ^2 in place of the global maximum; we treat (B2) as the primitive in the main analysis. Heuristic route for (D3). The differentiated-decay part of (D3) is expected to hold under the same contraction regime L~f<1 L_f<1, provided in addition that the score ∇jlogπj _ θ_j _j is uniformly bounded and Lipschitz in j θ_j (which is (D3)(i)). The reason is structural: ∇jQiπ _ θ_jQ_i^π and ∇jdπ _ θ_jd^π both satisfy influence recursions of the same distance-indexed form as the one used for (B2), but with the score derivative playing the role of the perturbation source. Differentiating the coupled-trajectory recursion in j θ_j introduces one extra bounded factor (the score θ-derivative, bounded by G′G ) at the agent-j node and otherwise propagates the discrepancy through the same contraction L~f<1 L_f<1. The front therefore reaches agent i after d(i,j)d(i,j) steps with geometric attenuation, giving ‖∇jQiπ‖≲ρd(i,j) _ θ_jQ_i^π ρ^d(i,j) and analogously for the occupancy sensitivity; the cross-parameter Hessian block ∂ij2J∂^2_ θ_i θ_jJ, which aggregates these component sensitivities (Appendix B, Step 1), then inherits the geometric decay postulated in (D3)(i). We emphasize that this is a sketch: a rigorous derivation requires the differentiated influence-cone recursion, and we therefore state (D3) as a primitive assumption rather than a consequence of (B2). Appendix B Derivation of LJ=(1)L_J=O(1) under the differentiated regularity (D3) This appendix shows that, under Assumption (D3), the Hessian ∇2J()∇^2J( θ) has operator norm bounded independently of the network size n on Θ0 _0, which justifies treating LJL_J as an n-uniform primitive in (D2). We stress at the outset what is and is not proved here: the geometric decay of the cross-parameter Hessian block ∂ij2J∂^2_ θ_i θ_jJ in graph distance is assumed as part of (D3)(i); it does not follow from the exponential decay (B2) of QiπQ_i^π itself, because differentiation in a policy parameter introduces score and occupancy sensitivities, and mixed second-order differences, that (B2) does not control. What this appendix establishes is the implication “(D3) ⇒ LJ=(1)L_J=O(1),” i.e. that the assumed per-block decay, once granted, sums to an n-uniform operator-norm bound on the Hessian. The argument follows the spatial-decay template of Qu et al. [22] adapted to the continuous-state policy-gradient setting. Step 0: Twice-differentiability and block structure By (D3)(i), each πi(⋅∣iκπ;i) _i(· s_N_i _π; θ_i) is twice continuously differentiable in i θ_i on the compact convex Θ0,i _0,i, with score ∇ilogπi _ θ_i _i bounded by G (Assumption (A3)) and Lipschitz in i θ_i with constant G′G . Since J()=μ0[∑iViπ((0))]J( θ)=E_ _0[ _iV_i^π(s^(0))] is a finite sum of discounted returns and the policy enters smoothly, dominated convergence (the integrands are uniformly bounded by QmaxQ_ and the relevant derivative families are uniformly bounded under (A3) and (D3)(i)) gives that J is twice continuously differentiable on the interior of Θ0 _0, and the second derivative extends continuously to the compact Θ0 _0. Write the Hessian in block form ∇2J()∈ℝndθ×ndθ,[∇2J]ij:=∂ij2J∈ℝdθ×dθ. aligned ∇^2J( θ)∈R^nd_θ× nd_θ, [∇^2J]_ij:=∂^2_ θ_i θ_jJ∈R^d_θ× d_θ. aligned (58) Step 1: Differentiating the per-agent policy-gradient identity Fix agents i,ji,j. Starting from the per-agent policy-gradient identity (5), ∇iJ()=11−γνπ[∑ℓ=1nQℓπ(,)i(,)], aligned _ θ_iJ( θ)= 11-γE_ν^π [ _ =1^nQ_ ^π(s,a)\, ψ_i(s,a) ], aligned (59) where i:=∇ilogπi(i∣iκπ) ψ_i:= _ θ_i _i(a_i s_N_i _π) is the agent-i score. Differentiating once more in j θ_j and using the product rule on the three j θ_j-dependent factors, namely the occupancy-times-policy measure νπν^π, the value QℓπQ_ ^π, and, only when j=ij=i, the score i ψ_i, gives ij=11−γ(νπ[∑ℓ(∇jQℓπ)i⊤]⏟=:TijQ+∑ℓνπ[Qℓπi(∇jlogνπ)⊤]⏟=:Tijν+νπ[∑ℓQℓπ(∂ji)]⏟=:Tijψ), aligned _ij&= 11-γ ( E_ν^π [ _ ( _ θ_jQ_ ^π)\, ψ_i ]_=:\,T^Q_ij\\ & + _ E_ν^π [Q_ ^π\, ψ_i\,( _ θ_j ν^π) ]_=:\,T^ν_ij\\ & + E_ν^π [ _ Q_ ^π\,( _ θ_j ψ_i) ]_=:\,T^ψ_ij ), aligned where the score-derivative block TijψT^ψ_ij is non-zero only when j=ij=i (since i ψ_i depends on j θ_j only through j=ij=i), and ∇jlogνπ _ θ_j ν^π denotes the score of the occupancy-policy measure with respect to j θ_j. These three terms are formal motivation for the mechanisms through which agents i and j couple in the curvature of J; the occupancy score ∇jlogνπ _ θ_j ν^π is shorthand for the signed-measure derivative ∂jνπ _ θ_jν^π since the discounted occupancy may carry a singular t=0t=0 component, the display is not used quantitatively, and the theorem below relies only on (D3)(i); throughout, the standing graph-tail hypothesis δ~:=(Δ−1)ρ<1 δ:=( -1)ρ<1 of (D3)(i) is in force. Step 2: Per-block geometric decay The differentiation under the expectation in Step 1 is justified as follows: ∇jlogνπ _ θ_j ν^π denotes the score of the discounted occupancy, defined through its finite-horizon truncations νTπ:=(1−γ)∑t≤Tγtℙt⊗πν^π_T:=(1-γ) _t≤ Tγ^t\,P_t π (whose densities are finite products of θ-differentiable policy factors along the trajectory, with scores bounded by tGtG), the limit T→∞T→∞ being exchanged with the expectation by dominated convergence against the geometric weights under the uniform bounds of (A3) and (D3)(i); the resulting object is used in the sequel only through the assumed decay (60) below, never through an explicit formula. Assumption (D3)(i) postulates the cross-block geometric decay directly, ‖[∇2J()]ij‖≤c′ρd(i,j),c′:=c∂, aligned [∇^2J( θ)]_ij ≤ c \,ρ^\,d(i,j), c :=c_∂, aligned (60) uniformly in ∈Θ0 θ∈ _0. We record why this is the natural curvature analogue of (B2) for the three terms identified in Step 1, rather than an unrelated hypothesis. In TijQT^Q_ij the score i ψ_i is conditionally mean-zero given the state and supported on iκπN_i _π, while ∇jQℓπ _ θ_jQ_ ^π carries a value sensitivity localized at agent j; the block thus couples i and j only through value sensitivities propagating along the graph. In TijνT^ν_ij the measure score ∇jlogνπ=∇jlogdπ+j _ θ_j ν^π= _ θ_j d^π+ ψ_j localizes a second sensitivity at j while i ψ_i localizes at i, with QℓπQ_ ^π coupling the two through (B2). In TijψT^ψ_ij, by (D3)(i), ∂ji _ θ_j ψ_i is non-zero only for j=ij=i and has operator norm at most G′G , so this term contributes only a bounded constant to the diagonal block and does not affect off-diagonal decay. A first-principles derivation of (60) from the primitive sensitivities of (A3) and (B2) would require controlling mixed second-order differences, namely the variation of an already-differentiated value in a second, distant agent’s action, which (B2) does not provide; we therefore take the cross-block decay (60) as the primitive content of (D3)(i), with constant c′=c∂c =c_∂ independent of n. The number of agents at exact graph distance r from a fixed agent is at most Δ(Δ−1)r−1 ( -1)^r-1 for r≥1r≥ 1 (and 11 for r=0r=0) on a graph of maximum degree Δ . Hence, for any fixed agent i, the operator norm of ∇2J∇^2J is bounded by its maximum block-row sum: ∑j=1n‖[∇2J]ij‖≤c′∑j=1nρd(i,j)≤c′(1+∑r≥1Δ(Δ−1)r−1ρr)=c′(1+Δ−1⋅δ~1−δ~). aligned _j=1^n [∇^2J]_ij &≤ c _j=1^nρ^d(i,j)\\ &≤ c (1+ _r≥ 1 ( -1)^r-1ρ^r )\\ &=c (1+ -1· δ1- δ ). aligned The right-hand side is finite under the standing graph-tail hypothesis δ~=(Δ−1)ρ<1 δ=( -1)ρ<1 of (D3)(i) and, crucially, is independent of n, because both the per-block decay constant c′c and the geometric block-row sum depend only on (Δ,ρ,c∂)( ,ρ,c_∂) and not on the network size. Step 3: Conclusion A symmetric block matrix has operator norm bounded by its maximum block-row sum (a block-matrix Gershgorin/Schur bound). Therefore LJ:=sup∈Θ0‖∇2J()‖op≤c′(1+Δ−1⋅δ~1−δ~)=(1), aligned L_J:= _ θ∈ _0 ∇^2J( θ) _ op≤ c (1+ -1· δ1- δ )=O(1), aligned (61) independent of n. This is exactly the n-uniformity invoked in (D2) and used in Corollary 1 and Theorem 6. The constant c′=c∂c =c_∂ is the cross-block curvature-decay constant of (D3)(i), and the block-row sum depends only on the graph parameters (Δ,δ~)( , δ) of (D3)(i); neither depends on n. Remark on the role of (D3). The single step that genuinely requires (D3) rather than (B2) is the per-block decay (60), which (D3)(i) postulates directly. Assumption (B2) controls only QℓπQ_ ^π itself and would not, on its own, yield the geometric decay of the cross-parameter Hessian block, since that block aggregates mixed second-order parameter sensitivities; this is precisely why (D3)(i) is stated as a separate primitive, and why this appendix establishes the implication ((D3) ⇒ LJ=(1)L_J=O(1)) by graph summation rather than deriving LJ=(1)L_J=O(1) from (B2) alone. Appendix C Continuity of the population TD matrix and measurability of EME_M Lemma 10. Under (A1) and (A3), for each fixed feature realization the map ↦i θ M_i θ is continuous on Θ0 _0 for every i; consequently ↦σmin(i) θ _ (M_i θ) is continuous, the infimum in (24) over the compact Θ0 _0 is attained, and the event EME_M is measurable with respect to the preprocessing σ-algebra. Proof. Fix the feature realization and i. By (A3) the score is bounded by G, so for ,′∈Θ0 θ, θ ∈ _0, every s, and a.e. ia_i on the common support isuppA_i supp of (A3), |logπi(i∣⋅;i)−logπi(i∣⋅;i′)|≤G∥i−i′∥ | _i(a_i ·; θ_i)- _i(a_i ·; θ_i ) |≤ G θ_i- θ_i , whence ∫|πi(⋅;i)−πi(⋅;i′)|i≤eG‖i−i′‖−1 | _i(·; θ_i)- _i(·; θ_i ) |\,da_i≤ e^G θ_i- θ_i -1, and by subadditivity of total variation over the product policy, TV(π(⋅∣),π′(⋅∣))≤∑j(eG‖j−j′‖−1)≤n(eG‖−′‖−1)=:ζTV( _ θ(· s), _ θ (· s))≤ _j(e^G θ_j- θ_j -1)≤ n\,(e^G θ- θ -1)=:ζ. The transition kernel does not depend on θ, so a coupling of the two chains started from the same μ0 _0 gives TV(ℙt,ℙt′)≤tζTV(P_t θ,P_t θ )≤ t\,ζ for the time-t state laws; hence TV(νπ,νπ′)≤(1−γ)∑t≥0γt(t+1)ζ=ζ/(1−γ)TV(ν _ θ,ν _ θ )≤(1-γ) _t≥ 0γ^t\,(t+1)\,ζ=ζ/(1-γ), and the law generating (,′)(Z,Z ) (one further policy factor for ′a ) satisfies the same bound with ζ/(1−γ)ζ/(1-γ) replaced by ζ/(1−γ)+ζ≤2ζ/(1−γ)ζ/(1-γ)+ζ≤ 2ζ/(1-γ). Each entry of iM_i θ is an expectation of a function bounded by (1+γ)L2(1+γ)L^2 under this law, so ‖i−i′‖≤‖i−i′‖F≤(m+1)⋅2(1+γ)L2⋅2ζ1−γ→′→0, aligned M_i θ-M_i θ &≤ M_i θ-M_i θ _F\\ &≤(m+1)· 2(1+γ)L^2· 2ζ1-γ [ θ → θ]0, aligned proving continuity; the same argument (with the reward factor bounded by r¯ r) covers ib_i θ. Since σmin _ is 11-Lipschitz in the operator norm and Θ0 _0 is compact, inf∈Θ0σmin(i) _ θ∈ _0 _ (M_i θ) is attained and equals the infimum over any countable dense subset Θ0d⊂Θ0 _0 d⊂ _0; as each ω↦i(ω)ω M_i θ(ω) is measurable in the feature randomness for fixed θ, the event EM=⋂i⋂∈Θ0dσmin(i)≥μM(m)E_M= _i _ θ∈ _0 d\ _ (M_i θ)≥ _M(m)\ is measurable. ∎ Appendix D Proof of Theorem 1 (RFF approximation) Fix an agent i and abbreviate d:=di,κ≤DκdSd:=d_i,κ≤ D_κd_S, g:=gα(i)g:=g_α^(i), p:=pα(i)p:=p_α^(i), and ():=i,κ()/1−α2u(Z):=f_i,κ(Z)/ 1-α^2. Writing Aℓ:=i,ℓ⊤()+bi,ℓA_ := ω_i, u(Z)+b_i, and Bℓ():=1−α2i,ℓ⊤+bi,ℓB_ (y):= 1-α^2\, ω_i, y+b_i, , the raw feature inner product is ⟨ϕi,κraw(),μi,κraw()⟩=g()p()k^m(,),k^m:=2m∑ℓ=1mcosAℓcosBℓ, aligned _i,κ raw(Z), _i,κ raw(y) &=g(Z)\,p(y)\, k_m(Z,y),\\ k_m&:= 2m _ =1^m A_ B_ , aligned with |k^m|≤2 | k_m |≤ 2 pointwise. By the product-to-sum identity, cosAℓcosBℓ=12cos(Aℓ−Bℓ)+12cos(Aℓ+Bℓ) A_ B_ = 12 (A_ -B_ )+ 12 (A_ +B_ ); the sum-frequency term carries the phase 2bi,ℓ2b_i, and averages to zero, while the difference term averages, by the Gaussian characteristic function of ∼(,σ−2d) ω N(0,σ^-2I_d), to 12k0(()−1−α2) 12k_0(u(Z)- 1-α^2\,y). Hence k^m=k0(()−1−α2)E\, k_m=k_0(u(Z)- 1-α^2\,y) and, by the splitting identity (10), the estimator is pointwise unbiased for ℙi,κ(∣)P_i,κ(y Z). Step 1 (uniform random-phase bound on the compact core). Define ℳ:=():∪1−α2:‖≤R2(ϵP)⊂ℝdM:=\u(Z):Z\∪\ 1-α^2\,y: y ≤ R_2( _P)\⊂R^d. By (A1), ‖()‖≤DκBf/1−α2 u(Z) ≤ D_κB_f/ 1-α^2 for every Z, so ℳM is bounded with diam(ℳ)≤2(DκBf/1−α2+R2(ϵP))≤2Dℛint(ϵP)diam(M)≤ 2( D_κB_f/ 1-α^2+R_2( _P))≤ 2D_R int( _P); we apply the random-feature bound on the closure ℳ¯ M, which is compact in ℝdR^d with the same diameter, and restrict the resulting uniform bound to ℳM. The estimator k^m(,′)=2m∑ℓcos(ℓ⊤+bℓ)cos(ℓ⊤′+bℓ) k_m(x,x )= 2m _ ( ω_ x+b_ ) ( ω_ x +b_ ) is exactly the random-phase Rahimi–Recht estimator of the shift-invariant kernel k0k_0 with spectral law (,σ−2d)N(0,σ^-2I_d), whose second moment is σp2:=‖2=d/σ2 _p^2:=E ω ^2=d/σ^2. Claim 1 of [24] gives, for every t>0t>0, ℙ(sup,′∈ℳ|k^m(,′)−k0(−′)|≥t)≤28(σpdiam(ℳ)t)2×exp(−mt24(d+2)). aligned &P ( _x,x ∈M | k_m(x,x )-k_0(x-x ) |≥ t )≤\\ & 2^8 ( _p\,diam(M)t )^2× (- m\,t^24(d+2) ). aligned Set t:=ϵP/(2g~α)t:= _P/(2 g_α) and require the right-hand side to be at most δrff/n _ rff/n; solving for m gives the sufficient condition m≥ 16(d+2)g~α2ϵP2×log(28n(4σpDℛint(ϵP)g~α/ϵP)2δrff), aligned m&\;≥\;16(d+2)\, g_α^2 _P^2\\ & × \! ( 2^8\,n\, (4\, _p\,D_R int( _P)\, g_α/ _P )^2 _ rff ), aligned which is (13) with CRFF(d)=16(d+2)C_ RFF(d)=16(d+2), after substituting σp2=DκdS/σ2 _p^2=D_κd_S/σ^2 (the factor 42σp24^2 _p^2 contributes 24DκdS/σ22^4D_κd_S/σ^2, and 28⋅24=2122^8· 2^4=2^12). Call the resulting event Erff(i)E_ rff^(i). Step 2 (weighted core error). On Erff(i)E_ rff^(i), for every Z (since ()∈ℳu(Z)∈M always, and 1−α2∈ℳ 1-α^2\,y∈M for ‖≤R2 y ≤ R_2), ∫‖≤R2gp|k0−k^m|≤tg¯α(κ)(2πσ2α2)d/2≤tg~α≤ϵP2, aligned _ y ≤ R_2g\,p\, |k_0- k_m |\,dy&≤ t\, g_α(κ) ( 2πσ^2α^2 )^d/2\\ &≤ t\, g_α\;≤\; _P2, aligned using ∫pα(i)=(2πσ2/α2)d/2 p_α^(i)=(2πσ^2/α^2)^d/2, the derived bound (11), and g¯α(2πσ2/α2)d/2≤g~α g_α(2πσ^2/α^2)^d/2≤ g_α (both cases of the maximum in the definition of g~α g_α, since d≤DκdSd≤ D_κd_S). Step 3 (true-kernel tail). Under ℙi,κ(⋅∣)P_i,κ(· Z) the successor is =i,κ()+y=f_i,κ(Z)+ with ∼(,σ2d) N(0,σ^2I_d). Since α∈(0,1)α∈(0,1) and d≤DκdSd≤ D_κd_S, R2(ϵP)≥DκBf+σ(d+2log(8g~α/ϵP))R_2( _P)≥ D_κB_f+σ( d+ 2 (8 g_α/ _P)), so Gaussian norm concentration gives ∫‖>R2ℙi,κ(∣)≤ϵP/(8g~α)≤ϵP/8 _ y >R_2P_i,κ(y Z)\,dy≤ _P/(8 g_α)≤ _P/8, using g~α≥1 g_α≥ 1. Step 4 (signed-approximant tail). Pointwise, |⟨ϕraw,μraw⟩|≤2g()p()≤2g¯αpα(i)() | φ raw,μ raw |≤ 2\,g(Z)\,p(y)≤ 2\, g_α\,p_α^(i)(y): the approximant is signed and need not integrate to one, but it is dominated by twice the Gaussian envelope. As pα(i)p_α^(i) is the unnormalized density of (,(σ2/α2)d)N(0,(σ^2/α^2)I_d) with total mass (2πσ2/α2)d/2(2πσ^2/α^2)^d/2, and R2(ϵP)≥(σ/α)(d+2log(8g~α/ϵP))R_2( _P)≥(σ/α)( d+ 2 (8 g_α/ _P)), writing ∼(,(σ2/α2)d) ξ N(0,(σ^2/α^2)I_d), ∫‖>R2|⟨ϕraw,μraw⟩|≤2g¯α(2πσ2α2)d/2ℙ(‖>R2)≤2g~α⋅ϵP8g~α=ϵP4, aligned _ y >R_2 | φ raw,μ raw |\,dy&≤ 2\, g_α ( 2πσ^2α^2 )^d/2P_ ξ ( ξ >R_2 )\\ &≤ 2\, g_α· _P8\, g_α= _P4, aligned Combining Steps 2–4 by the triangle inequality on ‖>R2\ y >R_2\, for every Z on Erff(i)E_ rff^(i), ∥ℙi,κ(⋅∣)−⟨ϕi,κraw(),μi,κraw(⋅)⟩∥ℒ1≤ϵP2+ϵP8+ϵP4<ϵP P_i,κ(· Z)- _i,κ raw(Z), _i,κ raw(·) _L^1≤ _P2+ _P8+ _P4< _P. Step 5 (agents, heterogeneous dimensions, normalization). A union bound over i∈[n]i∈[n] at confidence δrff/n _ rff/n each gives ℙ(⋂iErff(i))≥1−δrffP( _iE_ rff^(i))≥ 1- _ rff; the feasibility relation (13), evaluated at the worst case d=DκdSd=D_κd_S with the global constants g~α,Dℛint g_α,D_R int, dominates each agent’s requirement because 16(d+2)16(d+2) and the logarithm’s argument are nondecreasing in d. The normalization of Definition 1 preserves the inner product (ϕ^=ϕraw/g¯α φ=φ raw/ g_α, ^=μrawg¯α μ=μ raw g_α), so the same bound holds for ⟨ϕ^i,κ,^i,κ⟩ φ_i,κ, μ_i,κ , which is the event ErffE_ rff. □ Appendix E Proof of Lemma 2 (value decay) Let ,′s,s agree on iκN_i^κ. Couple two action draws ∼π(⋅∣)a π(· s), ′∼π(⋅∣′)a π(· s ) so that j=j′a_j=a_j for every j with jκπ⊆iκN_j _π N_i^κ; this is possible because π factorizes and each πj _j depends only on jκπs_N_j _π, which coincide for such j. The set of agents j with jκπ⊆iκN_j _π N_i^κ contains iκ−κπN_i^κ- _π. Hence (,)(s,a) and (′,′)(s ,a ) agree on iκ−κπN_i^κ- _π at the state-action level. By the V-to-Q relation Viπ()=∼π(⋅∣)[Qiπ(,)]V_i^π(s)=E_a π(· s)[Q_i^π(s,a)] and (B2) applied at radius κ−κπκ- _π, |Viπ()−Viπ(′)|≤cρ(κ−κπ)+1=cρ−κπρκ+1. aligned |V_i^π(s)-V_i^π(s ) |≤ cρ^(κ- _π)+1=cρ^- _πρ^κ+1. aligned (62) The derivation above holds without the factor 22; we retain it as harmless slack (any constant ≥1≥ 1 suffices), so that c~:=2cρ−κπ c:=2cρ^- _π also absorbs minor variants of the coupling construction, affecting only the constant in (B2)-derived bounds. □ Appendix F Proof of Proposition 1 Part (a) By Definition 2, Q¯iπ()=νπ[Qiπ(,)∣Xiκ=] Q_i^π(x)=E_ν^π[Q_i^π(S,A) X_i^κ=x]. Conditional on Xiκ=X_i^κ=x, any two realizations (,),(′,′)(S,A),(S ,A ) in the conditioning event agree on iκN_i^κ at the state-action level, so (B2) gives |Qiπ(,)−Qiπ(′,′)|≤cρκ+1 |Q_i^π(S,A)-Q_i^π(S ,A ) |≤ cρ^κ+1 a.s. Since Q¯iπ() Q_i^π(x) is a conditional average of QiπQ_i^π over exactly this event, |Qiπ(,)−Q¯iπ(Xiκ)|≤cρκ+1 |Q_i^π(S,A)- Q_i^π(X_i^κ) |≤ cρ^κ+1 νπν^π-a.s. □ Part (b): auxiliary residual The argument has two error sub-steps, E1 and E2, followed by a Banach perturbation. Step E1 (replacing ViπV_i^π by V¯iπ V_i^π). Starting from the genuine Bellman equation Qiπ(,)=ri(i,i)+γ[Viπ(′)∣,]Q_i^π(S,A)=r_i(S_N_i,A_N_i)+γE[V_i^π(S ) S,A] and taking νπ[⋅∣Xiκ=]E_ν^π[· X_i^κ=x] on both sides, Q¯iπ() Q_i^π(x) =[ri∣Xiκ=] =E[r_i X_i^κ=x] (63) +γνπ[Viπ(′)|Xiκ=]. +γ\,E_ν^π [V_i^π(S )\, |\,X_i^κ=x ]. Since κ≥1κ≥ 1, i⊆iκN_i N_i^κ, so ri(i,i)r_i(S_N_i,A_N_i) is a deterministic function of x and [ri∣Xiκ=]=ri()E[r_i X_i^κ=x]=r_i(x). For the continuation term, write iκ′S _N_i^κ for the restriction of the successor state to iκN_i^κ and decompose [Viπ(′)∣Xiκ=]=[V¯iπ(iκ′)|Xiκ=]+[Viπ(′)−V¯iπ(iκ′)|Xiκ=]. aligned E[V_i^π(S ) X_i^κ=x]&=E [ V_i^π(S _N_i^κ)\, |\,X_i^κ=x ]\\ & +E [V_i^π(S )- V_i^π(S _N_i^κ)\, |\,X_i^κ=x ]. aligned By Definition 2, V¯iπ()=dπ[Viπ()∣iκ=] V_i^π(s)=E_d^π[V_i^π(S) S_N_i^κ=s] is a convex average of ViπV_i^π over completions of the local component s. The successor ′S here is distributed under the one-step pushforward of νπν^π, which need not coincide with dπd^π; the discounted occupancy is not one-step invariant in general; we therefore do not assert that the second summand has conditional mean zero. Instead we use the oscillation envelope directly: for any full state ′s with local component iκ′s _N_i^κ, both Viπ(′)V_i^π(s ) and V¯iπ(iκ′) V_i^π(s _N_i^κ) are values of ViπV_i^π, respectively a pointwise value and a convex average of values, over completions sharing the local component iκ′s _N_i^κ, and by Lemma 2 the spread of ViπV_i^π over any such set of completions is at most c~ρκ+1 cρ^κ+1. Hence the second summand is bounded in absolute value, νπν^π-a.s., by c~ρκ+1 cρ^κ+1, with no appeal to invariance of dπd^π. Although V¯iπ V_i^π is defined only (Xiκ)#dπ(X_i^κ)_\#d^π-a.e., its evaluation at the successor argument iκ′S _N_i^κ is unambiguous for the chosen bounded measurable representative: from dπ=(1−γ)μ0+γPπ⊤dπd^π=(1-γ) _0+γ P_π d^π one has Pπ⊤dπ≪dπP_π d^π d^π, so the successor local marginal is absolutely continuous with respect to the dπd^π-local marginal. Hence |[Viπ(′)∣Xiκ=]−[V¯iπ(iκ′)∣Xiκ=]| |E[V_i^π(S ) X_i^κ=x]-E[ V_i^π(S _N_i^κ) X_i^κ=x] | (64) ≤c~ρκ+1. ≤ cρ^κ+1. Writing P¯i,κπ(d∣) P_i,κ^π(dy x) for the conditional law of iκ′S _N_i^κ given Xiκ=X_i^κ=x (Definition 2), (63)–(64) give |Q¯iπ()−ri()−γ∫V¯iπ()P¯i,κπ(d∣)| | Q_i^π(x)-r_i(x)-γ\! \! V_i^π(y)\, P_i,κ^π(dy x) | (65) ≤γc~ρκ+1. ≤γ cρ^κ+1. Step E2 (explicit Bellman-defect of V¯iπ V_i^π under the auxiliary operator). We now show that V¯iπ V_i^π is an approximate fixed point of the auxiliary local Bellman operator T¯π T^π of Definition 2, with an explicitly derived defect. This step replaces the compressed “tower plus E1” assertion of earlier drafts with a full derivation. Fix ∈iκs∈S_N_i^κ. By definition, V¯iπ()=[Viπ()∣iκ=] V_i^π(s)=E[V_i^π(S) S_N_i^κ=s]. Apply the genuine Bellman equation for the value function, Viπ()=∼π(⋅∣)[ri(i,i)+γ′[Viπ(′)∣,]]V_i^π(S)=E_A π(· S)[r_i(S_N_i,A_N_i)+γE_S [V_i^π(S ) S,A]], inside the conditional expectation and use the tower property over the conditioning σ-algebra σ(iκ)σ(S_N_i^κ): V¯iπ() V_i^π(s) =[ri(i,i)|iκ=] =E [r_i(S_N_i,A_N_i)\, |\,S_N_i^κ=s ] (66) +γ[Viπ(′)|iκ=]. +γ\,E [V_i^π(S )\, |\,S_N_i^κ=s ]. We compare (66) term-by-term with the auxiliary operator applied to V¯iπ V_i^π, (T¯πV¯iπ)() ( T^π V_i^π)(s) =∼πiκmarg[ri(,) =E_a π marg_N_i^κ [r_i(s,a) (67) +γ∫V¯iπ()P¯i,κπ(d∣,)]. +γ\! \! V_i^π(y)\, P_i,κ^π(dy s,a) ]. Reward terms cancel exactly. The marginal policy πiκmarg(d∣)π marg_N_i^κ(da s) and the conditional reward expectation [ri∣iκ=]E[r_i S_N_i^κ=s] are, by Definition 2, defined as conditional expectations under the same measure νπν^π and the same conditioning σ-algebra σ(iκ)σ(S_N_i^κ). Since rir_i depends only on (i,i)(S_N_i,A_N_i) and i⊆iκN_i N_i^κ, the reward term of (67) equals [ri(i,i)∣iκ=]E[r_i(S_N_i,A_N_i) S_N_i^κ=s], which is exactly the reward term of (66). Continuation terms differ only by a truncation substitution. The continuation term of (66) is γ[Viπ(′)∣iκ=]γE[V_i^π(S ) S_N_i^κ=s], the full-state value of the successor. The continuation term of (67), by the definition of P¯i,κπ P_i,κ^π as the conditional law of iκ′S _N_i^κ, equals γ[V¯iπ(iκ′)∣iκ=]γE[ V_i^π(S _N_i^κ) S_N_i^κ=s]. The two continuation terms therefore differ only in that Viπ(′)V_i^π(S ) is replaced by V¯iπ(iκ′) V_i^π(S _N_i^κ). Since V¯iπ(iκ′) V_i^π(S _N_i^κ) is a convex average of ViπV_i^π over completions agreeing on iκN_i^κ and Viπ(′)V_i^π(S ) is the value at one such completion, the difference Viπ(′)−V¯iπ(iκ′)V_i^π(S )- V_i^π(S _N_i^κ) is bounded in absolute value, νπν^π-a.s., by the oscillation of ViπV_i^π over completions agreeing on iκN_i^κ, which by Lemma 2 is at most c~ρκ+1 cρ^κ+1. This uses only the oscillation envelope and not a conditional-mean-zero property (which would require one-step invariance of dπd^π and need not hold). Hence |V¯iπ()−(T¯πV¯iπ)()| | V_i^π(s)-( T^π V_i^π)(s) | =γ|[Viπ(′)−V¯iπ(iκ′)∣iκ=]| =γ |E[V_i^π(S )- V_i^π(S _N_i^κ) S_N_i^κ=s] | (68) ≤γc~ρκ+1, ≤γ cρ^κ+1, uniformly in s, i.e. ‖V¯iπ−T¯πV¯iπ‖∞≤γc~ρκ+1 V_i^π- T^π V_i^π _∞≤γ cρ^κ+1. Step E3 (Banach perturbation). The operator T¯π T^π is a γ-contraction in the essential-supremum norm on the ℒ∞L^∞ space of Definition 2, evaluated on bounded measurable representatives, with unique fixed point V¯iπ,aux V_i^π, aux. The standard Banach perturbation estimate for a γ-contraction T states that if ‖v−v‖∞≤ϵ v-Tv _∞≤ε then ‖v−v∗‖∞≤ϵ/(1−γ) v-v _∞≤ε/(1-γ), where v∗v is the fixed point. Indeed, ‖v−v∗‖∞≤‖v−v‖∞+‖v−v∗‖∞≤ϵ+γ‖v−v∗‖∞ v-v _∞≤ v-Tv _∞+ Tv-Tv _∞≤ε+γ v-v _∞, and rearranging gives the bound. Applying this with v=V¯iπv= V_i^π, =T¯πT= T^π, and ϵ=γc~ρκ+1ε=γ cρ^κ+1 from (68), ‖V¯iπ−V¯iπ,aux‖∞≤γc~ρκ+11−γ. aligned V_i^π- V_i^π, aux _∞≤ γ cρ^κ+11-γ. aligned (69) Conclusion of Part (b). Define the residual Rκ()R_κ(x) by Rκ():=Q¯iπ()−ri()−γ∫V¯iπ,aux()P¯i,κπ(d∣), aligned R_κ(x):= Q_i^π(x)-r_i(x)-γ\! \! V_i^π, aux(y)\, P_i,κ^π(dy x), aligned (70) so that the displayed identity of Proposition 1(b) holds by construction. To bound RκR_κ, add and subtract the V¯iπ V_i^π-continuation term and apply the triangle inequality: |Rκ()|≤|Q¯iπ()−ri()−γ∫V¯iπ()P¯i,κπ(d∣)|+γ|∫(V¯iπ−V¯iπ,aux)()P¯i,κπ(d∣)|. aligned |R_κ(x) |&≤ | Q_i^π(x)-r_i(x)-γ\! \! V_i^π(y)\, P_i,κ^π(dy x) |\\ & +γ | \!( V_i^π- V_i^π, aux)(y)\, P_i,κ^π(dy x) |. aligned The first term is at most γc~ρκ+1γ cρ^κ+1 by (65). The second term is at most γ‖V¯iπ−V¯iπ,aux‖∞≤γ2c~ρκ+1/(1−γ)γ V_i^π- V_i^π, aux _∞≤γ^2 cρ^κ+1/(1-γ) by (69). Summing, esssup|Rκ|≤γc~ρκ+1(1+γ1−γ)=γc~ρκ+11−γ, aligned *ess\,sup |R_κ |≤γ cρ^κ+1 (1+ γ1-γ )= γ cρ^κ+11-γ, aligned (71) which is the bound stated in Proposition 1(b). □ Appendix G Proof of Theorem 2 (linear representation) On the favorable event ErffE_ rff at accuracy ϵP _P, the RFF inner product approximates the neighborhood kernel within ϵP _P in ℒ1L^1 uniformly in Z (Theorem 1). Applying this to the continuation integral in Proposition 1(b), |γ∫V¯iπ,aux()P¯i,κπ(d∣)−γ⟨ϕ~i,κπ(),i,κπ⟩2:m+1|≤γ‖V¯iπ,aux‖∞ϵP≤γr¯ϵP1−γ, aligned & |γ\! \! V_i^π, aux(y)\, P_i,κ^π(dy x)-γ φ_i,κ^π(x),w_i,κ^π _2:m+1 |\\ & ≤γ V_i^π, aux _∞\, _P≤ γ r\, _P1-γ, aligned where the subscript 2:m+12:m+1 denotes the RFF block of the augmented feature and weight, the first coordinate carries the reward, and we used ‖V¯iπ,aux‖∞≤r¯/(1−γ) V_i^π, aux _∞≤ r/(1-γ) from Definition 2. The first coordinate of ϕ~i,κπ φ_i,κ^π is [ri∣Xiκ=]=ri()E[r_i X_i^κ=x]=r_i(x) and the first coordinate of i,κπw_i,κ^π is 11, so ⟨ϕ~i,κπ(),i,κπ⟩=ri()+γ⟨ϕ~i,κπ(),i,κπ⟩2:m+1 φ_i,κ^π(x),w_i,κ^π =r_i(x)+γ φ_i,κ^π(x),w_i,κ^π _2:m+1. Combining with Proposition 1(b), Q¯iπ()=⟨ϕ~i,κπ(),i,κπ⟩+ξi(), aligned Q_i^π(x)= φ_i,κ^π(x),w_i,κ^π + _i(x), aligned (72) where ξi _i collects the RFF residual and RκR_κ, hence esssup|ξi|≤γr¯ϵP1−γ+esssup|Rκ|≤γr¯ϵP1−γ+γc~ρκ+11−γ=ξ¯i, aligned *ess\,sup | _i |≤ γ r _P1-γ+ *ess\,sup |R_κ |≤ γ r _P1-γ+ γ cρ^κ+11-γ= ξ_i, aligned (73) which is (22). □ Appendix H Proof of Lemma 4 (conditional projection error) Work throughout on the favorable event EM∩ErffE_M∩ E_ rff, so σmin(i)≥μM _ (M_i θ)≥ _M and the linear representation of Theorem 2 is in force. Step 1: the Bellman defect ρX _X. By Proposition 1(a), Q¯iπ Q_i^π differs from QiπQ_i^π by at most cρκ+1cρ^κ+1 a.s. The genuine Bellman equation for QiπQ_i^π, conditioned to the neighborhood variables, yields Q¯iπ(Xiκ)=ri(Xiκ)+γ[Q¯iπ(Xiκ′)∣Xiκ]+ρX, aligned Q_i^π(X_i^κ)=r_i(X_i^κ)+γ\,E[ Q_i^π(X_i^κ ) X_i^κ]+ _X, aligned (74) where Xiκ′X_i^κ is the one-step successor neighborhood variable and the Bellman defect ρX _X is the error of replacing Qiπ(′,′)Q_i^π(S ,A ) by Q¯iπ(Xiκ′) Q_i^π(X_i^κ ) in the successor term; the present-time identity Q¯iπ(Xiκ)=[Qiπ∣Xiκ] Q_i^π(X_i^κ)=E[Q_i^π X_i^κ] holds exactly by Definition 2 and contributes no error. By Proposition 1(a) applied to the successor term, |ρX|≤γcρκ+1 | _X |≤γ cρ^κ+1 νπν^π-a.s. where the bound is unconditional and does not require the confinement event, because Proposition 1(a) is an almost-sure statement. Step 2: the population normal equations and the error vector ∗E . Substitute the linear representation Q¯iπ()=⟨ϕ~i,κπ(),i,κπ⟩+ξi() Q_i^π(x)= φ_i,κ^π(x),w_i,κ^π + _i(x) of Theorem 2 into the Step-1 identity. Rearrange so that i,κπw_i,κ^π multiplies ϕ~i,κπ(Xiκ)−γ[ϕ~i,κπ(Xiκ′)∣Xiκ] φ_i,κ^π(X_i^κ)-γ\,E[ φ_i,κ^π(X_i^κ ) X_i^κ], then multiply by the raw augmented feature ϕ~i,κraw() φ_i,κ raw(Z) and take νπE_ν^π. Using [ϕ~i,κraw∣Xiκ]=ϕ~i,κπE[ φ_i,κ raw X_i^κ]= φ_i,κ^π and the tower property, every raw feature collapses to its conditional counterpart, so the matrix multiplying i,κπw_i,κ^π is the conditional-feature TD matrix iπ:=νπ[ϕ~i,κπ(ϕ~i,κπ−γϕ~i,κπ′)⊤], aligned M_i^π:=E_ν^π [ φ_i,κ^π( φ_i,κ^π-γ φ_i,κ^π ) ], aligned (75) while the reward term reproduces the raw target ib_i θ (as rir_i is XiκX_i^κ-measurable, [ϕ~i,κrawri]=[ϕ~i,κπri]=iE[ φ_i,κ rawr_i]=E[ φ_i,κ^πr_i]=b_i θ): iπi,κπ=i+∗, M_i^πw_i,κ^π=b_i θ+E , (76) ∗:=νπ[ϕ~i,κraw()e()], E =E_ν^π [ φ_i,κ raw(Z)\,e(Z) ], where the scalar error integrand is e():=ρX()−ξi(Xiκ())+γ[ξi(Xiκ′)∣Xiκ()]. aligned e(Z):= _X(Z)- _i(X_i^κ(Z))+γ\,E[ _i(X_i^κ ) X_i^κ(Z)]. aligned (77) Here the three contributions to e are, respectively, the Bellman defect of Step 1, the present-time linear-representation residual, and the discounted successor-time linear-representation residual. By the tower property, the successor term may be evaluated either before or after multiplication by ϕ~i,κraw φ_i,κ raw; we keep the conditional form. Bounding ∗E . The error vector ∗=νπ[ϕ~i,κraw()e()]E =E_ν^π[ φ_i,κ raw(Z)\,e(Z)] is an integral, so by Jensen’s inequality for Bochner integrals together with ‖ϕ~i,κraw‖≤L φ_i,κ raw ≤ L pointwise, ‖∗‖=‖νπ[ϕ~i,κrawe]‖≤νπ[‖ϕ~i,κraw‖|e|]≤Lνπ|e|. aligned E = E_ν^π [ φ_i,κ raw\,e ] ≤E_ν^π [ φ_i,κ raw \, |e | ]≤ L\,E_ν^π |e |. aligned (78) We bound the expectation νπ|e|E_ν^π |e |, rather than the essential supremum, by the triangle inequality, treating the three contributions to e separately. The expectation route is essential here: the off-confinement contribution is controlled only through the small probability mass of the failure region, and a small-probability event reduces an expectation but cannot reduce an essential supremum. (We do not absorb the Bellman defect into the linear-representation residual: ρX _X and ξi _i are distinct objects and the off-confinement contribution is not proportional to ξ¯i ξ_i.) • Bellman-defect contribution. By Step 1, |ρX|≤γcρκ+1 | _X |≤γ cρ^κ+1 νπν^π-a.s., hence νπ|ρX|≤γcρκ+1E_ν^π | _X |≤γ cρ^κ+1, unconditionally. • Linear-representation residual, on confinement. On the confinement region TδtrajS_T _ traj, Theorem 2 gives esssup|ξi|≤ξ¯i *ess\,sup | _i |≤ ξ_i. Restricted to this region the present-time and discounted-successor residual terms together contribute, in expectation, at most (1+γ)ξ¯i(1+γ) ξ_i (the confinement probability is at most 11). • Linear-representation residual, off confinement. Outside TδtrajS_T _ traj, boundedness of the truncated value, |Q¯iπ|≤Qmax | Q_i^π |≤ Q_ , together with the population-target ceiling ‖i,κπ‖≤U1 w_i,κ^π ≤ U_1 (Lemma 5, Step 1) and ‖ϕ~i,κπ‖≤L φ_i,κ^π ≤ L bounds the linear-representation residual ξi=Q¯iπ−⟨ϕ~i,κπ,i,κπ⟩ _i= Q_i^π- φ_i,κ^π,w_i,κ^π pointwise by |ξi|≤Qmax+LU1 | _i |≤ Q_ +LU_1; this is a population bound, not a statement about the implemented critic. Because the quantity being bounded is the expectation νπ|e|E_ν^π |e |, the off-confinement contribution is this pointwise bound weighted by the off-confinement probability mass δtraj+γT+1 _ traj+γ^T+1; the discounted-successor term carries the additional absolute-continuity factor 1+1/γ1+1/γ relating the one-step pushforward of νπν^π to dπd^π (from dπ≥γPπ⊤dπd^π≥γ\,P_π d^π). Collecting the present-time and discounted-successor off-confinement parts gives a contribution at most (1+γ)Eout(1+γ)E_ out, with Eout=(Qmax+LU1)(1+1/γ)(δtraj+γT+1)E_ out=(Q_ +LU_1)(1+1/γ)( _ traj+γ^T+1) exactly as in the lemma statement. This probability-weighting is legitimate precisely because the bounded quantity is an expectation. Collecting the three contributions, νπ|e|≤(1+γ)ξ¯i+(1+γ)Eout+γcρκ+1=(1+γ)ξ¯iaug+γcρκ+1, aligned E_ν^π |e |&≤(1+γ) ξ_i+(1+γ)E_ out+γ cρ^κ+1\\ &=(1+γ) ξ_i aug+γ cρ^κ+1, aligned (79) with ξ¯iaug:=ξ¯i+Eout ξ_i aug:= ξ_i+E_ out. Crucially, the Bellman-defect term γcρκ+1γ cρ^κ+1 is kept as an explicit additive term and is not merged into the (1+γ)ξ¯iaug(1+γ) ξ_i aug term: by Theorem 2, ξ¯i≥γc~ρκ+1/(1−γ)≥2γcρκ+1/(1−γ) ξ_i≥γ cρ^κ+1/(1-γ)≥ 2γ cρ^κ+1/(1-γ) (using c~=2cρ−κπ≥2c c=2cρ^- _π≥ 2c), so the Bellman-defect term satisfies γcρκ+1≤1−γ2ξ¯i≤12ξ¯iγ cρ^κ+1≤ 1-γ2 ξ_i≤ 12 ξ_i; we record this comparison for use in Step 4 but do not use it to inflate the coefficient of ξ¯iaug ξ_i aug. Hence ‖∗‖≤(1+γ)Lξ¯iaug+Lγcρκ+1. aligned E ≤(1+γ)L ξ_i aug+Lγ cρ^κ+1. aligned (80) Step 3: cross-covariance perturbation. The population LSTD solution is i∗=(i)−1iw_i =(M_i θ)^-1b_i θ. Subtracting (76), i∗−i,κπ=−(i)−1∗+(i)−1Mi,κπ, aligned w_i -w_i,κ^π=-(M_i θ)^-1E +(M_i θ)^-1 _Mw_i,κ^π, aligned (81) where M:=iπ−i _M:=M_i^π-M_i θ is the gap between the conditional-feature and raw-feature TD matrices. Expanding ϕ~i,κraw=ϕ~i,κπ+i φ_i,κ raw= φ_i,κ^π+ η_i and ϕ~i,κraw′=ϕ~i,κπ′+i′ φ_i,κ raw = φ_i,κ^π + η_i in iM_i θ and subtracting iπM_i^π produces six cross terms; the two equal-time terms [iϕ~i,κπ⊤]E[ η_i φ_i,κ^π ] and [ϕ~i,κπi⊤]E[ φ_i,κ^π η_i ] vanish, since ϕ~i,κπ φ_i,κ^π is XiκX_i^κ-measurable and [i∣Xiκ]=E[ η_i X_i^κ]=0, leaving the four within-bin cross-covariance terms M=−[ii⊤]+γ[ii′⊤]+γ[iϕ~i,κπ′⊤]+γ[ϕ~i,κπi′⊤]. aligned _M=-E[ η_i η_i ]+γE[ η_i η_i ]+γE[ η_i φ_i,κ^π ]+γE[ φ_i,κ^π η_i ]. aligned (82) By Jensen and the pointwise bounds ‖i‖≤2L η_i ≤ 2L, ‖ϕ~i,κπ‖≤L φ_i,κ^π ≤ L, the four terms have operator norm at most 4L24L^2, 4γL24γ L^2, 2γL22γ L^2, and 2γL22γ L^2 respectively; summing, ‖M‖≤4L2+8γL2=Cη(1+2γ)L2 _M ≤ 4L^2+8γ L^2=C_η(1+2γ)L^2 with Cη=4C_η=4. Step 4: assembling the bound. Using σmin(i)≥μM _ (M_i θ)≥ _M so that ‖(i)−1‖≤1/μM (M_i θ)^-1 ≤ 1/ _M, the triangle inequality and (80) give ‖i∗−i,κπ‖ w_i -w_i,κ^π ≤‖∗‖μM+‖M‖‖i,κπ‖μM ≤ E _M+ _M w_i,κ^π _M (83) ≤(1+γ)Lξ¯iaug+Lγcρκ+1μM ≤ (1+γ)L ξ_i aug+Lγ cρ^κ+1 _M +Cη(1+2γ)L2‖i,κπ‖μM. + C_η(1+2γ)L^2 w_i,κ^π _M. The displayed bound (83) is exactly the statement of Lemma 4: the explicit Bellman-defect term Lγcρκ+1/μMLγ cρ^κ+1/ _M is kept in the lemma rather than silently absorbed into the ξ¯iaug ξ_i aug term. The Step-2 comparison γcρκ+1≤12ξ¯i≤12ξ¯iaugγ cρ^κ+1≤ 12 ξ_i≤ 12 ξ_i aug records that the bare Bellman-defect term is dominated by the linear-representation residual. In Appendix K the weight-unit bound (83) is converted to Q-error units by the factor L (see (93) below), and the resulting Q-unit Bellman-defect contribution L2γcρκ+1/μML^2γ cρ^κ+1/ _M is absorbed there into the C′Etrunc(κ)C E_ trunc(κ) floor term, keeping the downstream constant C′=(1+γ)L2/μMC =(1+γ)L^2/ _M unchanged. This completes the proof of Lemma 4. □ Appendix I Proof of Lemma 5 Step 1: population-target ceiling U1U_1. By Definition 3 and (19), i,κπ=(1,γ∫^i,κ()V¯iπ,aux())w_i,κ^π= (1,\,γ\! μ_i,κ(y)\, V_i^π, aux(y)\,dy ). The first coordinate contributes 11. The passage from the raw to the conditional kernel uses conditional Jensen, ∥[ℙi,κ(⋅∣)−ℙ^i,κ(⋅∣)∣X]∥1≤[∥ℙi,κ−ℙ^i,κ∥1∣X]≤ϵP E[P_i,κ(· Z)- P_i,κ(· Z) X] _1≤E[ P_i,κ- P_i,κ _1 X]≤ _P on the random-feature event. The RFF block is a vector-valued Lebesgue integral over the unbounded domain ∈ℝdi,κy∈R^d_i,κ, so it must be controlled through the ℒ1L^1-mass of ^i,κ μ_i,κ, since a pointwise supremum alone does not bound an integral over an infinite-measure domain: ‖γ∫^i,κ()V¯iπ,aux()‖≤γ‖V¯iπ,aux‖∞∫‖^i,κ()‖. aligned γ\! μ_i,κ(y)\, V_i^π, aux(y)\,dy ≤γ\, V_i^π, aux _∞\! \! μ_i,κ(y) \,dy. aligned (84) We bound the ℒ1L^1-mass explicitly. By Definition 1, ^i,κ()=g¯αpα(i)()2/mcos(1−α2i,ℓ⊤+bi,ℓ)ℓ=1m μ_i,κ(y)= g_α\,p_α^(i)(y) 2/m\,\ ( 1-α^2\, ω_i, y+b_i, )\_ =1^m; since each of the m cosines lies in [−1,1][-1,1], the cosine vector has Euclidean norm at most m m, so ‖^i,κ()‖≤2g¯αpα(i)() μ_i,κ(y) ≤ 2\, g_α\,p_α^(i)(y) pointwise. The damping factor pα(i)()=exp(−α2‖2/(2σ2))p_α^(i)(y)= (-α^2 y ^2/(2σ^2)) of (9) is Lebesgue-integrable, with ∫ℝdi,κpα(i)()=(2πσ2/α2)di,κ/2 _R^d_i,κp_α^(i)(y)\,dy=(2πσ^2/α^2)^d_i,κ/2. Hence, using di,κ=|iκ|dS≤DκdSd_i,κ= |N_i^κ |d_S≤ D_κd_S and the definition g~α=g¯αmax1,(2πσ2/α2)DκdS/2 g_α= g_α \1,(2πσ^2/α^2)\^D_κd_S/2 of Theorem 1, ∫‖^i,κ()‖≤2g¯α(2πσ2/α2)di,κ/2≤2g~α, aligned μ_i,κ(y) \,dy≤ 2\, g_α\,(2πσ^2/α^2)^d_i,κ/2≤ 2\, g_α, aligned (85) the last step using that max1,xa \1,x\^a is non-decreasing in a≥0a≥ 0 and di,κ≤DκdSd_i,κ≤ D_κd_S. Combining the two displays with ‖V¯iπ,aux‖∞≤r¯/(1−γ) V_i^π, aux _∞≤ r/(1-γ) from Definition 2, and using ‖(1,)‖≤1+‖ (1,v) ≤ 1+ v for the augmented vector, ‖i,κπ‖≤1+2γg~αr¯1−γ=U1. aligned w_i,κ^π ≤ 1+ 2\,γ g_α r1-γ=U_1. aligned (86) Step 2: from projection error to ‖i∗‖ w_i . By the triangle inequality and Lemma 4, ‖i∗‖≤‖i,κπ‖+‖i∗−i,κπ‖≤U1+(1+γ)Lξ¯iaug+Lγcρκ+1μM+Cη(1+2γ)L2U1μM, aligned w_i &≤ w_i,κ^π + w_i -w_i,κ^π \\ &≤ U_1+ (1+γ)L ξ_i aug+Lγ cρ^κ+1 _M+ C_η(1+2γ)L^2U_1 _M, aligned where we used ‖i,κπ‖≤U1 w_i,κ^π ≤ U_1 in the within-bin term and retained the explicit Bellman-defect term from (83). Collecting the U1U_1-proportional terms into KbinU1K_ binU_1 with Kbin=1+Cη(1+2γ)L2/μMK_ bin=1+C_η(1+2γ)L^2/ _M, and splitting ξ¯iaug=ξ¯i+Eout ξ_i aug= ξ_i+E_ out, ‖i∗‖≤KbinU1+(1+γ)Lξ¯i+Lγcρκ+1μM+(1+γ)LEoutμM. aligned w_i ≤ K_ binU_1+ (1+γ)L ξ_i+Lγ cρ^κ+1 _M+ (1+γ)LE_ out _M. aligned (87) Step 3: bounding the ξ¯i ξ_i-term into W0W_0. Substitute ξ¯i=γr¯ϵP/(1−γ)+γc~ρκ+1/(1−γ) ξ_i=γ r _P/(1-γ)+γ cρ^κ+1/(1-γ) from Theorem 2 and use 1+γ≤21+γ≤ 2: (1+γ)Lξ¯iμM≤2Lγr¯ϵP(1−γ)μM+2Lγc~ρκ+1(1−γ)μM. aligned (1+γ)L ξ_i _M≤ 2Lγ r _P(1-γ) _M+ 2Lγ cρ^κ+1(1-γ) _M. aligned (88) The explicit Bellman-defect term Lγcρκ+1/μMLγ cρ^κ+1/ _M is combined with the truncation part of the previous display. Using c≤c~/2c≤ c/2 (from c~=2cρ−κπ≥2c c=2cρ^- _π≥ 2c), 2Lγc~ρκ+1(1−γ)μM+Lγcρκ+1μM≤2Lγc~ρκ+1(1−γ)μM+Lγc~ρκ+12μM≤8Lc~ρκ+1(1−γ)μM, aligned 2Lγ cρ^κ+1(1-γ) _M+ Lγ cρ^κ+1 _M&≤ 2Lγ cρ^κ+1(1-γ) _M+ Lγ cρ^κ+12 _M\\ &≤ 8L cρ^κ+1(1-γ) _M, aligned since 2γ/(1−γ)+γ/2≤8/(1−γ)2γ/(1-γ)+γ/2≤ 8/(1-γ) for all γ∈(0,1)γ∈(0,1) (the factor 88 leaves margin). Hence the U1U_1-, ϵP _P-, and ρκ+1ρ^κ+1-contributions assemble exactly into W0W_0 as defined in (30), and ‖i∗‖≤W0+(1+γ)LEoutμM. aligned w_i ≤ W_0+ (1+γ)LE_ out _M. aligned (89) Step 4: no-circularity and containment in the radius W∗=2W0W =2W_0. The constant W0W_0 depends only on the primitives (L,γ,r¯,g~α,c~,ρ,κ,μM,ϵP)(L,γ, r, g_α, c,ρ,κ, _M, _P) and not on W∗W ; the only remaining term in the bound on ‖i∗‖ w_i not already included in W0W_0 is the additive EoutE_ out-term, which is a fixed small quantity proportional to δtraj+γT+1 _ traj+γ^T+1. Under the side condition δtraj+γT+1≤μMW0/[(1+γ)L(Qmax+LU1)(1+1/γ)] _ traj+γ^T+1≤ _MW_0/[(1+γ)L(Q_ +LU_1)(1+1/γ)] stated in the lemma, the EoutE_ out-term is at most W0W_0, so ‖i∗‖≤2W0=W∗ w_i ≤ 2W_0=W : the deterministic projection radius W∗=2W0W =2W_0, fixed from primitives alone, contains the population target, and there is no circular dependence between the radius and the parameter choices (W∗W carries no ϵε-, δtraj _ traj-, or T-dependence). □ Appendix J Proof of Theorem 3 (LSTD concentration) Work on EM∩ErffE_M∩ E_ rff and fix (i,k)(i,k); write =(k) θ= θ^(k), =iM=M_i θ, (k)=i(k)M^(k)=M_i^(k), (k)=i(k)b^(k)=b_i^(k), ∗=i∗w =w_i . Conditional on ℱk−F_k^-, the MsM_s transitions in s(k)D_s^(k) are i.i.d. from the one-step law of (D1). Step 1: matrix-Bernstein for (k)−M^(k)-M. Each summand ϕ~raw((j))(ϕ~raw((j))−γϕ~raw(′(j)))⊤ φ raw(z^(j))( φ raw(z^(j))-γ φ raw(z (j))) is a (generally non-symmetric) (m+1)×(m+1)(m+1)×(m+1) matrix bounded in operator norm by (1+γ)L2(1+γ)L^2, with the conditional mean M. Apply the matrix-Bernstein inequality [29, Thm. 6.1.1] to the centered i.i.d. sum via the Hermitian dilation ℋ():=(⊤)H(X):= pmatrix0&X\\ X &0 pmatrix, which is required because the summands are non-symmetric and converts the operator-norm deviation of X into the spectral-norm deviation of the symmetric ℋ()H(X). The dilation has dimension 2(m+1)2(m+1), contributing a log(2(m+1)) (2(m+1)) factor, absorbed into log(m+1) (m+1) up to constants. With probability ≥1−δ/2≥ 1-δ/2 over s(k)D_s^(k), ‖(k)−‖≤CM′L2log((m+1)/δ)Ms, aligned M^(k)-M ≤ C_M L^2 ((m+1)/δ)M_s, aligned (90) for Ms≥C0L4log((m+1)/δ)/μM2M_s≥ C_0L^4 ((m+1)/δ)/ _M^2 chosen so that the linear matrix-Bernstein term is dominated by the sub-Gaussian term and the right-hand side is at most μM/4 _M/4. Step 2: dimension-free vector concentration for the centered target. Define the centered vector i(k):=(k)−(k)∗ ζ_i^(k):=b^(k)-M^(k)w , whose conditional mean is i−∗=b_i θ-Mw =0 by the definition of ∗w . Each i.i.d. summand of i(k) ζ_i^(k) is a mean-zero random vector in the finite-dimensional Hilbert space ℝm+1R^m+1, bounded in norm by B:=L(r¯+(1+γ)LW∗)B:=L( r+(1+γ)LW ) (using ‖ϕ~raw‖≤L φ raw ≤ L, |ri|≤r¯ |r_i |≤ r, ‖∗‖≤W∗ w ≤ W ). The Hilbert-space Hoeffding-type inequality of Pinelis [21, Thm. 3.5] for bounded mean-zero vectors (a Hilbert space is (2,1)(2,1)-smooth, so D=1D=1) gives a dimension-free deviation bound: with probability ≥1−δ/2≥ 1-δ/2 over s(k)D_s^(k), ‖i(k)‖≤CvBlog(1/δ)Ms. aligned ζ_i^(k) ≤ C_vB (1/δ)M_s. aligned (91) We emphasize that this bound carries no m m or log(m+1) (m+1) dimensional factor: Pinelis’s inequality for vectors in a separable Hilbert space is proved by a martingale/22-smoothness argument, not by a dilation or trace device, and its constant is genuinely dimension-free. The displayed bound of Theorem 3 writes log((m+1)/δ) ((m+1)/δ) in place of log(1/δ) (1/δ) in this term; this is a harmless upper bound, since log(1/δ)≤log((m+1)/δ) (1/δ)≤ ((m+1)/δ), and is retained only so that the two terms of the theorem can be displayed under a common logarithmic factor for compatibility with the matrix-Bernstein term of Step 1. No genuine dimensional dependence is introduced; the vector-concentration term remains dimension-free in substance. Step 3: assembling the LSTD error. On the intersection of the two favorable events of Steps 1–2 (probability ≥1−δ≥ 1-δ), the reverse-triangle bound (Remark 1) gives σmin((k)+λ)≥μM−μM/4−λ≥μM/2 _ (M^(k)+λI)≥ _M- _M/4-λ≥ _M/2 under λ≤μM/4λ≤ _M/4, so (k)+λM^(k)+λI is non-singular and the degenerate fallback of Definition 4 is not triggered. Writing ^i(k),raw−∗=((k)+λ)−1(i(k)−λ∗) w_i^(k), raw-w =(M^(k)+λI)^-1( ζ_i^(k)-λw ) and bounding, ‖^i(k),raw−∗‖≤2μM(‖i(k)‖+λ‖∗‖)≤2CvBμMlog((m+1)/δ)Ms+2λW∗μM, aligned w_i^(k), raw-w &≤ 2 _M ( ζ_i^(k) +λ w )\\ &≤ 2C_vB _M ((m+1)/δ)M_s+ 2λ W _M, aligned which is the stated bound with B=L(r¯+(1+γ)LW∗)B=L( r+(1+γ)LW ). The uniform version follows by replacing δ with δ/(nK)δ/(nK) and union-bounding over i∈[n]i∈[n], k<Kk<K. □ Appendix K Proof of Theorem 4 (local parameter selection) Fix (i,k)(i,k) and work on EM∩ErffE_M∩ E_ rff. The pointwise error of the critic decomposes, via Theorem 2 and the triangle inequality, into a statistical part EstatE_ stat (from the LSTD concentration of Theorem 3), a projection part EprojE_ proj (from Lemma 4), and the linear-representation residual ξ¯i ξ_i, with the local-to-global lift handled by Proposition 1(a). Statistical part and the choice of λ∗,Ms∗λ ,M_s . By Theorem 3, with τ:=log((m+1)/δ⋆)/Msτ:= ((m+1)/ _ )/M_s and Bδ:=r¯+(1+γ)LW∗B_δ:= r+(1+γ)LW , Estat≤2CvL2BδτμM+2λLW∗μM, aligned E_ stat≤ 2C_vL^2B_δ\,τ _M+ 2λ LW _M, aligned (92) where the second term is the regularization bias 2λLW∗/μM2λ LW / _M (the factor L converting weight error to Q-error). Since the derived bound contains no term that improves with λ, it is minimized at λ∗=0λ =0; the variance allocation τ=μMϵQ/(2CvL2Bδ)τ= _M _Q/(2C_vL^2B_δ), i.e. Ms∗=~(L6W∗2/(μM2ϵQ2))M_s = O(L^6W 2/( _M^2 _Q^2)), then gives Estat≤ϵQE_ stat≤ _Q. If a positive implementation value is used instead (Remark 1), any λ≤μMϵQ/(4LW∗)λ≤ _M _Q/(4LW ) contributes additional bias at most ϵQ/2 _Q/2 and satisfies the side condition λ≤μM/4λ≤ _M/4 because ϵQ≤LW∗ _Q≤ LW , the standing hypothesis of the theorem; the conclusion then holds with ϵQ _Q replaced by 32ϵQ 32 _Q, absorbed into the suppressed constants. Projection part and the floor constants. By Lemma 4 and the explicit Bellman-defect bookkeeping of Appendix H, the projection error in Q-units (multiplying the weight error by ‖ϕ~raw‖≤L φ raw ≤ L) is Eproj E_ proj ≤(1+γ)L2ξ¯iaug+L2γcρκ+1μM ≤ (1+γ)L^2 ξ_i aug+L^2γ cρ^κ+1 _M (93) +Cη(1+2γ)L3U1μM. + C_η(1+2γ)L^3U_1 _M. We now show (93) is bounded by C′(Etrunc(κ)+Erff(m)+Eout)+CbinC (E_ trunc(κ)+E_ rff(m)+E_ out)+C_ bin with C′=(1+γ)L2/μMC =(1+γ)L^2/ _M and Cbin=Cη(1+2γ)L3U1/μMC_ bin=C_η(1+2γ)L^3U_1/ _M unchanged. First, ξ¯iaug=ξ¯i+Eout ξ_i aug= ξ_i+E_ out and, by Theorem 2, ξ¯i≤Erff(m)+12Etrunc(κ) ξ_i≤ E_ rff(m)+ 12E_ trunc(κ): indeed γr¯ϵP/(1−γ)=Erff(m)γ r _P/(1-γ)=E_ rff(m) and γc~ρκ+1/(1−γ)≤12Etrunc(κ)γ cρ^κ+1/(1-γ)≤ 12E_ trunc(κ) since Etrunc(κ)=c~ρκ+1(1+2/(1−γ))E_ trunc(κ)= cρ^κ+1(1+2/(1-γ)) and γ/(1−γ)≤12(1+2/(1−γ))γ/(1-γ)≤ 12(1+2/(1-γ)) for γ∈(0,1)γ∈(0,1). Hence the first term of (93) satisfies (1+γ)L2ξ¯iaugμM≤C′(Erff(m)+12Etrunc(κ)+Eout). aligned (1+γ)L^2 ξ_i aug _M≤ C (E_ rff(m)+ 12E_ trunc(κ)+E_ out ). aligned (94) Second, the explicit Bellman-defect term: γcρκ+1≤12c~ρκ+1≤12Etrunc(κ)γ cρ^κ+1≤ 12 cρ^κ+1≤ 12E_ trunc(κ) (using c≤c~/2c≤ c/2 and Etrunc(κ)≥c~ρκ+1E_ trunc(κ)≥ cρ^κ+1), so L2γcρκ+1/μM≤C′⋅12Etrunc(κ)/(1+γ)≤C′⋅12Etrunc(κ)L^2γ cρ^κ+1/ _M≤ C · 12E_ trunc(κ)/(1+γ)≤ C · 12E_ trunc(κ). Adding the two truncation half-contributions yields the full C′Etrunc(κ)C E_ trunc(κ), and the third term of (93) is exactly CbinC_ bin. Therefore Eproj≤C′(Etrunc(κ)+Erff(m)+Eout)+Cbin, aligned E_ proj≤ C (E_ trunc(κ)+E_ rff(m)+E_ out )+C_ bin, aligned (95) with C′C and CbinC_ bin exactly as defined in Section V. The explicit Bellman-defect term has been absorbed into the truncation floor without changing C′C , as anticipated in Appendix H, Step 4. Assembling the bound. The linear-representation residual contributes ξ¯i≤(1+C′)−1(1+C′)(Etrunc+Erff) ξ_i≤(1+C )^-1(1+C )(E_ trunc+E_ rff), and combining Estat≤ϵQE_ stat≤ _Q with EprojE_ proj and the lift of Proposition 1(a) gives esssup|Q¯i^i(k)−Qiπ|≤ϵQ+(1+C′)(Etrunc+Erff)+Cbin+C′Eout, aligned *ess\,sup | Q_i w_i^(k)-Q_i^π |≤ _Q&+(1+C )(E_ trunc+E_ rff)\\ &+C_ bin+C E_ out, aligned (96) which is (36) with R(κ,m)=(1+C′)(Etrunc(κ)+Erff(m))+CbinR(κ,m)=(1+C )(E_ trunc(κ)+E_ rff(m))+C_ bin. The total failure probability δM+δrff+δ⋆ _M+ _ rff+ _ accounts for the two preprocessing events and the per-iteration LSTD event; the uniform version replaces δ⋆ _ by δ⋆/(nK) _ /(nK). □ Appendix L Proof of Lemma 7 (critic L2L^2 error) By Theorem 4, on the favorable events the conditional-feature critic obeys esssup|Q¯i^i(k)−Qiπ|≤ϵQ+R(κ,m)+C′Eout *ess\,sup | Q_i w_i^(k)-Q_i^π |≤ _Q+R(κ,m)+C E_ out on the confinement region. The deployed critic Q^i(k)()=ϕ~i,κraw()⊤^i(k) Q_i^(k)(z)= φ_i,κ raw(z) w_i^(k) evaluates the raw augmented feature, whereas Q¯i^i(k)=⟨ϕ~i,κπ,^i(k)⟩ Q_i w_i^(k)= φ_i,κ^π, w_i^(k) uses the conditional feature; by ϕ~i,κraw=ϕ~i,κπ+i φ_i,κ raw= φ_i,κ^π+ η_i the two differ by the within-bin fluctuation i⊤^i(k) η_i w_i^(k), of magnitude at most ‖i‖‖^i(k)‖≤2LW∗ η_i \, w_i^(k) ≤ 2LW pointwise. Hence on the favorable events the deployed critic satisfies the pointwise bound |Q^i(k)−Qiπ|≤ϵQ+[R(κ,m)+C′Eout]+2LW∗. aligned | Q_i^(k)-Q_i^π |≤ _Q+ [R(κ,m)+C E_ out ]+2LW . aligned (97) We convert this into an L2L^2-in-expectation bound. Let ℰE denote the intersection of the LSTD favorable event and the confinement event; by the parameter choices δ⋆=δtraj=ϵQ2/(3(LW∗+Qmax)2) _ = _ traj= _Q^2/(3(LW +Q_ )^2) and γT+1≤δ⋆γ^T+1≤ _ , the three failure contributions, namely LSTD, trajectory confinement, and horizon truncation, sum to at most 3δ⋆3 _ , so the complement ℰcE^c has probability at most 3δ⋆3 _ . On ℰE the squared error is at most (ϵQ+[R(κ,m)+C′Eout]+2LW∗)2( _Q+[R(κ,m)+C E_ out]+2LW )^2 by (97); on ℰcE^c the deterministic projection bound |Q^i(k)|≤LW∗ | Q_i^(k) |≤ LW together with |Qiπ|≤Qmax |Q_i^π |≤ Q_ gives squared error at most (LW∗+Qmax)2(LW +Q_ )^2. Hence algνπ[|Q^i(k)−Qiπ|2]≤(ϵQ+[R+C′Eout]+2LW∗)2+3δ⋆(LW∗+Qmax)2. aligned E_ algE_ν^π [ | Q_i^(k)-Q_i^π |^2 ]&≤ ( _Q+[R+C E_ out]+2LW )^2\\ & +3 _ (LW +Q_ )^2. aligned The second term equals ϵQ2 _Q^2 by the choice of δ⋆ _ . Applying (a+b)2≤2a2+2b2(a+b)^2≤ 2a^2+2b^2 to the first term with a=ϵQa= _Q and b=[R+C′Eout]+2LW∗b=[R+C E_ out]+2LW gives 2ϵQ2+2([R+C′Eout]+2LW∗)22 _Q^2+2([R+C E_ out]+2LW )^2. With Rtot(κ,m):=2[R(κ,m)+C′Eout]+2LW∗R_ tot(κ,m):= 2[R(κ,m)+C E_ out]+2LW one has Rtot≥[R+C′Eout]+2LW∗R_ tot≥[R+C E_ out]+2LW (since 2≥1 2≥ 1 and all terms are non-negative), so 2([R+C′Eout]+2LW∗)2≤2Rtot(κ,m)22([R+C E_ out]+2LW )^2≤ 2R_ tot(κ,m)^2. Collecting terms yields the stated bound 3ϵQ2+2Rtot(κ,m)23 _Q^2+2R_ tot(κ,m)^2; the additive 2LW∗2LW inside RtotR_ tot is exactly the direct pointwise within-bin contribution carried through (97), rather than being inserted by fiat. The truncation horizon T=⌈log(1/δ⋆)/log(1/γ)⌉−1T= (1/ _ )/ (1/γ) -1 specified in the lemma statement is the smallest integer ensuring γT+1≤δ⋆γ^T+1≤ _ . □ Appendix M Proof of Lemma 8 (gradient bias) Work conditional on ℱkQF_k^Q, so the critics ^ℓ(k)\ w_ ^(k)\ are fixed and g(k)D_g^(k) is i.i.d. from dπ(k)⊗π(k)d^π^(k) π^(k). The bias of ^i(k) g_i^(k) relative to ∇iJ((k)) _ θ_iJ( θ^(k)) decomposes into two sources: (i) the critic-approximation error within the κc _c-neighborhood, and (i) the aggregation error from truncating the global value sum ∑ℓQℓπ _ Q_ ^π to the neighborhood sum ∑ℓ∈iκcQ^ℓ(k) _ ∈N_i _c Q_ ^(k). Critic-approximation route. The per-agent policy-gradient identity (5) and the estimator (37) differ, on the κc _c-neighborhood, by the score-weighted critic error. Using ‖∇ilogπi‖≤G _ θ_i _i ≤ G, |iκc|≤Dκc |N_i _c |≤ D_ _c, and the L2L^2-critic bound of Lemma 7 together with Jensen (|⋅|≤(|⋅|2)1/2E |· |≤(E |· |^2)^1/2), (i)≤GDκc1−γ(3ϵQ+2Rtot(κ,m)). aligned (i)≤ GD_ _c1-γ ( 3\, _Q+ 2\,R_ tot(κ,m) ). aligned (98) Aggregation route. The truncated value sum omits the agents ℓ∉iκc ∉N_i _c, so route (i) equals 11−γ‖νπ[∑ℓ∉iκcQℓπ∇ilogπi]‖ 11-γ E_ν^π[ _ ∉N_i _cQ_ ^π\, _ θ_i _i] . We first establish a single-coordinate score-decoupling bound. Fix ℓ with d(i,ℓ)>κcd(i, )> _c. Under νπ=dπ⊗πν^π=d^π π the joint policy factorizes, so conditional on S the actions are independent across agents and the score satisfies [∇ilogπi(i∣iκπ)∣,−i]=i∼πi[∇ilogπi]=E[ _ θ_i _i(A_i S_N_i _π) S,A_-i]=E_A_i _i[ _ θ_i _i]=0, the score identity. Hence, for any function Q~ℓ Q_ of (,)(S,A) that does not depend on the single coordinate iA_i, ‖νπ[Qℓπ∇ilogπi]‖=‖νπ[(Qℓπ−Q~ℓ)∇ilogπi]‖≤Gesssup|Qℓπ−Q~ℓ|. aligned E_ν^π[Q_ ^π\, _ θ_i _i] &= E_ν^π[(Q_ ^π- Q_ )\, _ θ_i _i] \\ &≤ G\, *ess\,sup |Q_ ^π- Q_ |. aligned Take Q~ℓ Q_ to be QℓπQ_ ^π with the coordinate ia_i frozen at an arbitrary fixed value. The tuple (,)(S,A) and its ia_i-frozen counterpart agree on ℓd(i,ℓ)−1N_ ^\,d(i, )-1, since agent i lies outside that neighborhood; the exponential decay (B2) at radius d(i,ℓ)−1d(i, )-1 therefore gives esssup|Qℓπ−Q~ℓ|≤cρd(i,ℓ) *ess\,sup |Q_ ^π- Q_ |≤ cρ^\,d(i, ). Thus ‖νπ[Qℓπ∇ilogπi]‖≤Gcρd(i,ℓ) E_ν^π[Q_ ^π\, _ θ_i _i] ≤ Gc\,ρ^\,d(i, ), with no κπ _π-dependent shift in the exponent: the zero-mean cancellation is taken over the single coordinate iA_i, not over the score-support neighborhood iκπN_i _π. Summing over the omitted agents, with at most Δ(Δ−1)r−1 ( -1)^r-1 agents at graph distance r and δ~:=(Δ−1)ρ<1 δ:=( -1)ρ<1, (i)≤G1−γ∑ℓ:d(i,ℓ)>κcρd(i,ℓ)≤Gc1−γ∑r>κcΔ(Δ−1)r−1ρr=Gc(1−γ)(1−δ~)⋅Δ−1δ~κc+1=:ϵagg(κ), aligned (i)&≤ G1-γ _ :\,d(i, )> _cc\,ρ^\,d(i, )≤ Gc1-γ _r> _c ( -1)^r-1ρ^r\\ &= Gc(1-γ)(1- δ)· -1\, δ _c+1=: _ agg(κ), aligned which is (40). Summing (i) and (i) gives (39). The κπ=0 _π=0 specialization. When κπ=0 _π=0, the score ∇ilogπi(i∣i) _ θ_i _i(a_i s_i) depends only on agent i’s own state and action. Conditioning on ℱkQF_k^Q and on σ(Xℓκ)σ(X_ ^κ), the within-bin fluctuation route in the critic-approximation term vanishes by tower (the fixed critic ^ℓ(k) w_ ^(k) and the conditional-mean property [ℓ∣Xℓκ]=E[ η_ X_ ^κ]=0), so the direct pointwise within-bin contribution 2LW∗2LW inside RtotR_ tot may be replaced by 0; the argument uses that the deployed critic is linear in ϕ~raw φ raw (no value clipping) and that the raw/conditional split is performed before any application of Jensen or Cauchy–Schwarz, so the within-bin route is exactly [ℓ⊤^ℓ(k)∇ilogπi∣ℱkQ]E[ η_ w_ ^(k)\, _ θ_i _i F_k^Q] and the tower argument applies verbatim. □ Appendix N Proof of Lemma 9 We bound ϵb2=supk,iQ^∥[^i(k)∣Q^,(k)]−∇iJ∥2 _b^2= _k,iE_ Q E[ g_i^(k) Q, θ^(k)]- _ θ_iJ ^2, i.e. the expectation over the critic randomness Q Q of the Q Q-conditional squared bias. We do not square the fully-averaged bound of Lemma 8 directly; instead we use the Q Q-conditional decomposition that underlies it. Conditional on ℱkQF_k^Q the critics ^ℓ(k)\ w_ ^(k)\ are fixed, and the two routes of Appendix M give ∥[^i(k)∣Q^,(k)]−∇iJ∥≤G1−γ∑ℓ∈iκcνπ[|Q^ℓ(k)−Qℓπ||Q^]+ϵagg(κ), aligned & E[ g_i^(k) Q, θ^(k)]- _ θ_iJ \\ & ≤ G1-γ _ ∈N_i _cE_ν^π [ | Q_ ^(k)-Q_ ^π |\, |\, Q ]+ _ agg(κ), aligned the first term being the critic-approximation route (score bounded by G, neighborhood size |iκc|≤Dκc |N_i _c |≤ D_ _c, triangle inequality) and the second the aggregation route, which is deterministic. The bound holds Q Q-conditionally because, given ℱkQF_k^Q, the gradient sample g(k)D_g^(k) is i.i.d. from νπν^π and each Q^ℓ(k) Q_ ^(k) is a fixed function. Applying (a+b)2≤2a2+2b2(a+b)^2≤ 2a^2+2b^2 and then the Cauchy–Schwarz inequality over the at most DκcD_ _c summands, Q^∥[^i(k)∣Q^,(k)]−∇iJ∥2≤2ϵagg(κ)2+2G2Dκc(1−γ)2∑ℓ∈iκcQ^νπ[|Q^ℓ(k)−Qℓπ||Q^]2. aligned &E_ Q E[ g_i^(k) Q, θ^(k)]- _ θ_iJ ^2\\ & ≤ 2 _ agg(κ)^2+ 2G^2D_ _c(1-γ)^2 _ ∈N_i _cE_ Q\,E_ν^π [ | Q_ ^(k)-Q_ ^π |\, |\, Q ]^2. aligned By conditional Jensen, νπ[|Q^ℓ(k)−Qℓπ|∣Q^]2≤νπ[|Q^ℓ(k)−Qℓπ|2∣Q^]E_ν^π[ | Q_ ^(k)-Q_ ^π | Q]^2≤E_ν^π[ | Q_ ^(k)-Q_ ^π |^2 Q]; taking Q^E_ Q and invoking the L2L^2-critic bound of Lemma 7, namely algνπ|Q^ℓ(k)−Qℓπ|2≤3ϵQ2+2Rtot(κ,m)2E_ algE_ν^π | Q_ ^(k)-Q_ ^π |^2≤ 3 _Q^2+2R_ tot(κ,m)^2 for each ℓ , the sum over the DκcD_ _c neighbors is at most Dκc(3ϵQ2+2Rtot(κ,m)2)D_ _c(3 _Q^2+2R_ tot(κ,m)^2). Substituting, ϵb2≤2ϵagg(κ)2+2G2Dκc2(3ϵQ2+2Rtot(κ,m)2)(1−γ)2. aligned _b^2≤ 2 _ agg(κ)^2+ 2G^2D_ _c^2 (3 _Q^2+2R_ tot(κ,m)^2 )(1-γ)^2. aligned (99) This is sharper than the displayed bound (41), which carries 6ϵQ2+4Rtot26 _Q^2+4R_ tot^2 in place of 3ϵQ2+2Rtot23 _Q^2+2R_ tot^2; the displayed form is a factor-22 relaxation, retained as stated, and is therefore also valid. □ The κπ=0 _π=0 reduction. When κπ=0 _π=0, do not pass to |Q^ℓ(k)−Qℓπ| | Q_ ^(k)-Q_ ^π |. Instead, decompose inside the conditional expectation, Q^ℓ(k)−Qℓπ=(⟨ϕ~ℓ,κπ,^ℓ(k)⟩−Qℓπ)+ℓ⊤^ℓ(k) Q_ ^(k)-Q_ ^π=( φ_ ,κ^π, w_ ^(k) -Q_ ^π)+ η_ w_ ^(k). Given ℱkQF_k^Q the coefficient ^ℓ(k) w_ ^(k) is fixed, ∇ilogπi _ θ_i _i is σ(Xℓκ)σ(X_ ^κ)-measurable (as κc=κ _c=κ and i∈ℓκi∈N_ ^κ), and νπ[ℓ∣Xℓκ]=E_ν^π[ η_ X_ ^κ]=0, so νπ[(ℓ⊤^ℓ(k))∇ilogπi]=E_ν^π[( η_ w_ ^(k))\, _ θ_i _i]=0, and the Q Q-conditional bias involves only the conditional-feature errors ⟨ϕ~ℓ,κπ,^ℓ(k)⟩−Qℓπ φ_ ,κ^π, w_ ^(k) -Q_ ^π. Repeating the failure-budget accounting of the proof of Lemma 7 for this critic, whose favorable-event essential-supremum bound is ϵQ+R(κ,m)+C′Eout _Q+R(κ,m)+C E_ out directly from Theorem 4, and whose off-event deterministic bound is |⟨ϕ~ℓ,κπ,^ℓ(k)⟩|≤L‖^ℓ(k)‖≤LW∗ | φ_ ,κ^π, w_ ^(k) |≤ L w_ ^(k) ≤ LW together with |Qℓπ|≤Qmax |Q_ ^π |≤ Q_ , gives algνπ|⟨ϕ~ℓ,κπ,^ℓ(k)⟩−Qℓπ|2≤3ϵQ2+2(2[R(κ,m)+C′Eout])2E_ algE_ν^π | φ_ ,κ^π, w_ ^(k) -Q_ ^π |^2≤ 3 _Q^2+2( 2\,[R(κ,m)+C E_ out])^2. Substituting this bound in place of Lemma 7’s in the display above yields (41) with RtotR_ tot replaced by 2[R(κ,m)+C′Eout] 2\,[R(κ,m)+C E_ out], i.e. with 2LW∗2LW deleted. □ Appendix O Proof of Theorem 5 (convergence) By (D2), J is LJL_J-smooth on Θ0 _0. Write ^(k)=∇J((k))+(k) g^(k)=∇ J( θ^(k))+e^(k) with total error (k):=(k)+(k)e^(k):=b^(k)+n^(k), where (k):=[^(k)∣ℱkQ]−∇J((k))b^(k):=E[ g^(k) F_k^Q]-∇ J( θ^(k)) is the conditional bias and (k)n^(k) the conditionally mean-zero noise, and define the stochastic projected-gradient mapping ~η(k):=η−1(ΠΘ0((k)+η^(k))−(k)) G_η^(k):=η^-1( _ _0( θ^(k)+η g^(k))- θ^(k)), so that (k+1)=(k)+η~η(k) θ^(k+1)= θ^(k)+η G_η^(k). Why the classical noise accounting fails under projection. No inequality of the form J((k+1))≥J((k))+cη‖η((k))‖2−Cη2LJ‖(k)‖2EJ( θ^(k+1))≥EJ( θ^(k))+c\,η\,E G_η( θ^(k)) ^2-Cη^2L_J\,E n^(k) ^2 can hold on a constrained set: mean-zero noise can produce an expected objective decrease of order Θ(η) (η) at a point where η=G_η=0. A one-dimensional witness: Θ0=[0,1] _0=[0,1], J(x)=−x−x2/2J(x)=-x-x^2/2 (so LJ=1L_J=1), x=0x=0, noise ξ=+2ξ=+2 with probability 1/31/3 and ξ=−1ξ=-1 with probability 2/32/3; then η(0)=0G_η(0)=0 yet [J(x+)]−J(0)=−η/3−η2/6E[J(x^+)]-J(0)=-η/3-η^2/6. We therefore argue through the stochastic mapping, following the composite-optimization route of Ghadimi, Lan, and Zhang [12] (see also [13] for the unconstrained analogue). Step 1 (pathwise one-step inequality). The projection optimality condition for (k+1)=ΠΘ0((k)+η^(k)) θ^(k+1)= _ _0( θ^(k)+η g^(k)), tested at the feasible point (k) θ^(k), (using that Θ0 _0 is closed and convex, as each Θ0,i _0,i is compact convex by (A4)) reads ⟨(k)+η^(k)−(k+1),(k)−(k+1)⟩≤0 θ^(k)+η g^(k)- θ^(k+1), θ^(k)- θ^(k+1) ≤ 0, i.e. ⟨^(k),~η(k)⟩≥‖~η(k)‖2 g^(k), G_η^(k) ≥ G_η^(k) ^2. Combining with the LJL_J-smoothness lower bound and Young’s inequality ⟨(k),~η(k)⟩≤12‖(k)‖2+12‖~η(k)‖2 e^(k), G_η^(k) ≤ 12 e^(k) ^2+ 12 G_η^(k) ^2, J((k+1))≥J((k))+η⟨∇J((k)),~η(k)⟩−LJη22‖~η(k)‖2≥J((k))+η2(1−LJη)‖~η(k)‖2−η2‖(k)‖2, aligned J( θ^(k+1))&≥ J( θ^(k))+η ∇ J( θ^(k)), G_η^(k) - L_Jη^22 G_η^(k) ^2\\ &≥ J( θ^(k))+ η2 (1-L_Jη ) G_η^(k) ^2- η2 e^(k) ^2, aligned and with η≤1/(4LJ)η≤ 1/(4L_J) the coefficient of ‖~η(k)‖2 G_η^(k) ^2 is at least 3η/83η/8. Step 2 (from the stochastic to the true mapping). Non-expansiveness of ΠΘ0 _ _0 gives ‖η((k))−~η(k)‖≤‖(k)‖ G_η( θ^(k))- G_η^(k) ≤ e^(k) , hence ‖~η(k)‖2≥12‖η((k))‖2−‖(k)‖2 G_η^(k) ^2≥ 12 G_η( θ^(k)) ^2- e^(k) ^2. Substituting into Step 1 yields the pathwise inequality J((k+1))≥J((k))+3η16‖η((k))‖2−7η8‖(k)‖2, aligned J( θ^(k+1))≥ J( θ^(k))+ 3η16 G_η( θ^(k)) ^2- 7η8 e^(k) ^2, aligned (100) in which the error now enters, correctly, at order η per step. This inequality holds on every sample path before any expectation is taken; it is exactly the inequality that the predictable-prefix argument of Appendix Q multiplies by the indicator A0∩⋯∩AkErff1_A_0∩·s∩ A_k1_E_ rff. Step 3 (bias–variance and aggregation). Taking expectations and using that (k)b^(k) is ℱkQF_k^Q-measurable while [(k)∣ℱkQ]=E[n^(k) F_k^Q]=0 gives ‖(k)‖2=‖(k)‖2+‖(k)‖2E e^(k) ^2=E b^(k) ^2+E n^(k) ^2. All norms are aggregate quantities; under the product structure (A4), ‖2=∑i=1n‖i‖2 v ^2= _i=1^n v_i ^2 and the projection acts blockwise, so the analyzed update equals the global projected step. Since (k)=(i(k))i=1nb^(k)=(b_i^(k))_i=1^n stacks the per-agent biases, ‖(k)‖2=∑i‖i(k)‖2≤nϵb2E b^(k) ^2= _iE b_i^(k) ^2≤ n\, _b^2 by Lemma 9; and since (k)n^(k) stacks the per-agent mean-zero noises, ‖(k)‖2≤nσg2/MgE n^(k) ^2≤ n\, _g^2/M_g, where σg2=G2Dκc2(LW∗)2/(1−γ)2 _g^2=G^2D_ _c^2(LW )^2/(1-γ)^2 bounds the per-agent per-sample gradient-noise variance (the per-sample gradient magnitude is at most GDκcLW∗/(1−γ)GD_ _cLW /(1-γ) under the projected linear critic) and the division by MgM_g reflects the average over MgM_g i.i.d. samples. Step 4 (telescoping). Summing Step 2 over k=0,…,K−1k=0,…,K-1, using ΔJ=J∗−J((0)) _J=J -J( θ^(0)), dividing by 3ηK/163η K/16 and then by n: the explicit factor n in the error terms cancels against the division by n, while the descent term retains the factor 1/n1/n. This yields (42) with universal constants C1,C2,C3C_1,C_2,C_3 (one may take C1=16/3C_1=16/3 and C2=C3=14/3C_2=C_3=14/3). The per-agent normalization is a consequence of the product structure, not an assumed scaling. □ Appendix P Proof of Theorem 6 Substitute the parameter choices into Corollary 1. The descent term is (LJΔJ/(nK))=(LJ/K)O(L_J _J/(nK))=O(L_J/K) using ΔJ=(n) _J=O(n) (i.e. ΔJ≤2nQmax _J≤ 2nQ_ ); setting K∗=(LJ/ϵ)K =O(L_J/ε) makes it (ϵ)O(ε). The gradient-noise term (σg2/Mg)O( _g^2/M_g) is (ϵ)O(ε) for Mg∗=(σg2/ϵ)M_g =O( _g^2/ε). The bias-squared term, by Lemma 9, splits into (ϵagg(κ)2)O( _ agg(κ)^2), (G2Dκc2ϵQ2/(1−γ)2)O(G^2D_ _c^2 _Q^2/(1-γ)^2), and (G2Dκc2Rtot2/(1−γ)2)O(G^2D_ _c^2R_ tot^2/(1-γ)^2). The choice ϵQ=((1−γ)ϵ/(GDκc)) _Q=O((1-γ) ε/(GD_ _c)) makes the second contribution (ϵ)O(ε) and forces Ms∗=~(L6W∗2G2Dκc2/(μM2(1−γ)2ϵ))M_s = O(L^6W 2G^2D_ _c^2/( _M^2(1-γ)^2ε)) through Theorem 4. The remaining contributions, namely ϵagg(κ)2 _ agg(κ)^2 and the RtotR_ tot-part, which decomposes into within-bin, truncation, and RFF pieces, are, after absorbing the C′EoutC E_ out contribution, exactly the four components of the structural floor ϵfloor(κ,m) _ floor(κ,m) of (43). The absorption is explicit: with A:=LW∗+QmaxA:=LW +Q_ and B:=Qmax+LU1≤AB:=Q_ +LU_1≤ A (since W∗≥U1W ≥ U_1), the choices δ⋆=δtraj=ϵQ2/(3A2) _ = _ traj= _Q^2/(3A^2) and γT+1≤δ⋆γ^T+1≤ _ give Eout=B(1+1/γ)(δtraj+γT+1)≤2(1+1/γ)3ϵQ2/A=(ϵQ2)E_ out=B(1+1/γ)( _ traj+γ^T+1)≤ 2(1+1/γ)3\, _Q^2/A=O( _Q^2), hence (C′Eout)2=(ϵQ4)=(ϵ2)⊆(ϵ)(C E_ out)^2=O( _Q^4)=O(ε^2) O(ε) for ϵ≤ϵ0ε≤ _0; the elementary inequality (a+b+c+d)2≤4(a2+b2+c2+d2)(a+b+c+d)^2≤ 4(a^2+b^2+c^2+d^2) applied to RtotR_ tot routes this piece into the ϵε-budget without cross terms against the floor components. Hence 1nK∗∑k‖η((k))‖2≤ϵ+ϵfloor(κ,m). aligned 1nK _kE G_η( θ^(k)) ^2≤ε+ _ floor(κ,m). aligned (101) The total shared-oracle count is Nglobal=K∗(Ms∗+Mg∗)N_ global=K (M_s +M_g ); with K∗=(LJ/ϵ)K =O(L_J/ε) and Ms∗,Mg∗=~(1/ϵ)M_s ,M_g = O(1/ε) this is ~(1/ϵ2) O(1/ε^2). The per-iteration LSTD failure events and the confinement-failure mass are absorbed into the ϵε-budget via δ⋆=δtraj=ϵQ2/(3(LW∗+Qmax)2) _ = _ traj= _Q^2/(3(LW +Q_ )^2) with γT+1≤δ⋆γ^T+1≤ _ , exactly as in Lemma 7. □ Appendix Q Proof of Theorem 7 The only structural difference from Appendix P is that the TD-stability lower bound μM _M is replaced by μtraj _ traj and holds only on the trajectory event Etraj=⋂k<K∗AkE_ traj= _k<K A_k, with each Ak=infiσmin(i(k))≥μtrajA_k=\ _i _ (M_i θ^(k))≥ _ traj\ being ℱk−F_k^--measurable (predictable). Predictable-event factorization. The per-step descent inequality of Appendix O (Step 2 there, established pathwise before expectations) requires the LSTD bound only at the current iterate (k) θ^(k), which is controlled by AkA_k. Multiply the per-step inequality by the predictable indicator A0∩⋯∩AkErff∈ℱk−1_A_0∩·s∩ A_k1_E_ rff∈F_k^- before taking expectations. Because the indicator is ℱk−F_k^--measurable, it commutes with the conditional expectation in the concentration step (Theorem 3 applied conditional on ℱk−F_k^-), so the conditional matrix-Bernstein and Hilbert-space vector-concentration (Pinelis) bounds hold verbatim on Ak∩ErffA_k∩ E_ rff. No conditioning on the global future event EtrajE_ traj is used. Stopped-process telescoping. Define the stopping time τ:=infk:Akc∧K∗τ:= \k:A_k^c\ K , which is a valid stopping time for the filtration (ℱk−)(F_k^-) since τ>k=A0∩⋯∩Ak∈ℱk−\τ>k\=A_0∩·s∩ A_k∈F_k^-. Telescoping the predictable-prefix-weighted per-step inequality over k=0,…,K∗−1k=0,…,K -1 is equivalent to telescoping the descent inequality over the stopped process (k)k<τ\ θ^(k)\_k<τ on ErffE_ rff; the telescoped objective increments satisfy the pathwise identity ∑k<τ[J((k+1))−J((k))]=J((τ))−J((0))≤ΔJ _k<τ[J( θ^(k+1))-J( θ^(k))]=J( θ^(τ))-J( θ^(0))≤ _J, which is the only property of the stopped sum the argument uses; no sign condition on any boundary term is needed. This yields the unconditional predictable-prefix bound [1nK∗∑k=0K∗−1‖η((k))‖2 1A0∩⋯∩Ak 1Erff]≤ϵ+ϵfloor(κ,m), aligned E [ 1nK _k=0^K -1 G_η( θ^(k)) ^2\,1_A_0∩·s∩ A_k\,1_E_ rff ]≤ε+ _ floor(κ,m), aligned (102) which is statement (a); the equivalent stopped-process form follows from A0∩⋯∩Ak=τ>k1_A_0∩·s∩ A_k=1_\τ>k\. Statement (b) follows because Etraj⊆A0∩⋯∩AkE_ traj A_0∩·s∩ A_k for every k, whence Etraj≤A0∩⋯∩Ak1_E_ traj≤1_A_0∩·s∩ A_k. Statement (c) is Assumption 5 together with ℙ(Erff)≥1−δrffP(E_ rff)≥ 1- _ rff and a union bound, and statement (d) follows by dividing the bound of statement (b) by ℙ(Etraj∩Erff)≥1/2P(E_ traj∩ E_ rff)≥ 1/2. The complexity count Nglobaltraj=K∗(Ms∗+Mg∗)N_ global traj=K (M_s +M_g ) carries the factor LJL_J in both terms through K∗=(LJ/ϵ)K =O(L_J/ε), with all derived constants (W∗,C′,Cbin,ϵfloorW ,C ,C_ bin, _ floor) recomputed using μtraj _ traj in place of μM _M. □ Appendix R Proof of Proposition 4 (adaptive locality) Under the strengthened hypothesis Δρ<1 ρ<1, the graph-tail base satisfies δ~=(Δ−1)ρ<Δρ<1 δ=( -1)ρ< ρ<1 with margin. By the definitions of ϵfloortrunc _ floor trunc and ϵfloorgraph _ floor graph in (43), ϵfloortrunc(κ)∝ρ2(κ+1) _ floor trunc(κ) ρ^2(κ+1) and ϵfloorgraph(κ)∝δ~2(κc+1) _ floor graph(κ) δ^2( _c+1); both decay geometrically in κ. The two implicit inequalities defining κ∗κ are sufficient conditions, up to the displayed universal constants, for ϵfloortrunc(κ∗)≤ϵ/Cfloor _ floor trunc(κ )≤ε/C_ floor and ϵfloorgraph(κ∗)≤ϵ/Cfloor _ floor graph(κ )≤ε/C_ floor after taking logarithms, with the κ-dependent constant Ct(κ)C_t(κ) entering the truncation condition through C′(κ)C (κ). Hypothesis (i) bounds Ct(κ∗)≤Ct(μ¯M(m))C_t(κ )≤ C_t( μ_M(m)) uniformly, so the fixed-point inequality has a solution in [[1,κmax]][\![1, _ ]\!] whenever the displayed value lies in that range; the conservative explicit alternative replaces Ct(κ∗)C_t(κ ) by the finite supremum C¯t C_t. With κ∗κ so chosen, the convergence bound of Theorem 6 gives ϵε from the optimization and statistical terms and, through the outer constant in (43), Cfloor⋅(ϵ/Cfloor)=ϵC_ floor·(ε/C_ floor)=ε from each of ϵfloortrunc(κ∗) _ floor trunc(κ ) and ϵfloorgraph(κ∗) _ floor graph(κ ), leaving the surviving floor Cfloor[ϵfloorbin(κ∗;m)+ϵfloorrff(m;κ∗)]C_ floor[ _ floor bin(κ ;m)+ _ floor rff(m;κ )], hence the stated bound. Since g~α(κ)=exp((DκdS)) g_α(κ)= (O(D_κd_S)) and κ∗=(log(1/ϵ))κ =O( (1/ε)), substituting the relevant upper bound on Dκ∗D_κ ((κ∗)O(κ ), (κ∗p)O(κ p), or (Δκ∗)O( ^κ )) yields the polynomial, quasi-polynomial, and stretched-exponential upper envelopes of the statement, respectively; when the realized Dκc∗D_ _c reaches n, the cap Dκc∗≤nD_ _c ≤ n contributes the explicit n2n^2 factor of Remark 2. □ References [1] A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan (2021) On the theory of policy gradient methods: optimality, approximation, and distribution shift. Journal of Machine Learning Research 22 (98), p. 1–76. Cited by: §I-A. [2] Y. Arjevani, Y. Carmon, J. C. Duchi, D. J. Foster, N. Srebro, and B. Woodworth (2023) Lower bounds for non-convex stochastic optimization. Mathematical Programming 199 (1), p. 165–214. Cited by: §I-A, Theorem 6. [3] M. E. Baran and F. F. Wu (1989) Network reconfiguration in distribution systems for loss reduction and load balancing. IEEE Transactions on Power delivery 4 (2), p. 1401–1407. Cited by: §I-A. [4] J. Bhandari, D. Russo, and R. Singal (2018) A finite time analysis of temporal difference learning with linear function approximation. In Conference on Learning Theory (COLT), p. 1691–1692. Cited by: §I-A. [5] J. A. Boyan (2002) Technical update: least-squares temporal difference learning. Machine learning 49 (2), p. 233–246. Cited by: §I-A. [6] S. J. Bradtke and A. G. Barto (1996) Linear least-squares algorithms for temporal difference learning. Machine learning 22 (1), p. 33–57. Cited by: §I-A. [7] T. Chu, S. Chinchali, and S. Katti (2020) Multi-agent reinforcement learning for networked system control. arXiv preprint arXiv:2004.01339. Cited by: §I-A, §I-A. [8] T. Doan, S. Maguluri, and J. Romberg (2019) Finite-time analysis of distributed td (0) with linear function approximation on multi-agent reinforcement learning. In International Conference on Machine Learning, p. 1626–1635. Cited by: §I-A, §I-A. [9] P. Dobruschin (1968) The description of a random field by means of conditional probabilities and conditions of its regularity. Theory of Probability & Its Applications 13 (2), p. 197–224. Cited by: §I-C. [10] J. Feng, Y. Shi, G. Qu, S. H. Low, A. Anandkumar, and A. Wierman (2023) Stability constrained reinforcement learning for decentralized real-time voltage control. IEEE Transactions on Control of Network Systems 11 (3), p. 1370–1381. Cited by: §I-A, §I. [11] J. Foerster, G. Farquhar, T. Afouras, N. Nardelli, and S. Whiteson (2018) Counterfactual multi-agent policy gradients. In Proceedings of the AAAI conference on artificial intelligence, Vol. 32. Cited by: §I-A. [12] S. Ghadimi, G. Lan, and H. Zhang (2016) Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming 155 (1), p. 267–305. Cited by: Appendix O. [13] S. Ghadimi and G. Lan (2013) Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization 23 (4), p. 2341–2368. Cited by: Appendix O. [14] S. Iqbal and F. Sha (2019) Actor-attention-critic for multi-agent reinforcement learning. In International conference on machine learning, p. 2961–2970. Cited by: §I-A, §VII-A. [15] A. Lazaric, M. Ghavamzadeh, and R. Munos (2012) Finite-sample analysis of least-squares policy iteration. The Journal of Machine Learning Research 13 (1), p. 3041–3074. Cited by: §I-A. [16] Y. Lin, J. Gan, G. Qu, Y. Kanoria, and A. Wierman (2022) Decentralized online convex optimization in networked systems. In International Conference on Machine Learning, p. 13356–13393. Cited by: §I-A, §I-A. [17] Y. Lin, G. Qu, L. Huang, and A. Wierman (2021) Multi-agent reinforcement learning in stochastic networked systems. Advances in neural information processing systems 34, p. 7825–7837. Cited by: §I-A, §I-A, TABLE I, §I, §I-B. [18] F. Liu, X. Huang, Y. Chen, and J. A. Suykens (2021) Random features for kernel approximation: a survey on algorithms, theory, and beyond. IEEE Transactions on Pattern Analysis and Machine Intelligence 44 (10), p. 7128–7148. Cited by: §I-A. [19] R. Lowe, Y. I. Wu, A. Tamar, J. Harb, O. Pieter Abbeel, and I. Mordatch (2017) Multi-agent actor-critic for mixed cooperative-competitive environments. Advances in neural information processing systems 30. Cited by: §I-A. [20] K. S. Narendra and A. M. Annaswamy (2012) Stable adaptive systems. Courier Corporation. Cited by: §I-A, §V-A. [21] I. Pinelis (1994) Optimum bounds for the distributions of martingales in banach spaces. The Annals of Probability, p. 1679–1706. Cited by: Appendix J, §I-A, §V-B. [22] G. Qu, A. Wierman, and N. Li (2020) Scalable reinforcement learning of localized policies for multi-agent networked systems. In Learning for Dynamics and Control, p. 256–266. Cited by: Appendix B, §I-A, §I-A, TABLE I, §I, §I-B. [23] G. Qu, A. Wierman, and N. Li (2022) Scalable reinforcement learning for multiagent networked systems. Operations Research 70 (6), p. 3601–3628. Cited by: §I-A, §I. [24] A. Rahimi and B. Recht (2007) Random features for large-scale kernel machines. Advances in neural information processing systems 20. Cited by: Appendix D, §I-A. [25] P. Rebeschini and R. van Handel (2015) Can local particle filters beat the curse of dimensionality?. The Annals of Applied Probability 25 (5), p. 2809–2866. Cited by: §I-C. [26] Z. Ren, R. Zhang, B. Dai, and N. Li (2024) Scalable spectral representations for multi-agent reinforcement learning in network mdps. arXiv preprint arXiv:2410.17221. Cited by: item 2, §I-A, §I-A, TABLE I, §I-B. [27] S. Shin, Y. Lin, G. Qu, A. Wierman, and M. Anitescu (2023) Near-optimal distributed linear-quadratic regulator for networked systems. SIAM Journal on Control and Optimization 61 (3), p. 1113–1135. Cited by: §I-A. [28] R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour (1999) Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems 12. Cited by: §I-A, §I-B. [29] J. A. Tropp (2015) An introduction to matrix concentration inequalities. Foundations and trends® in machine learning 8 (1-2), p. 1–230. Cited by: Appendix J, §I-A. [30] R. Vershynin (2018) High-dimensional probability: an introduction with applications in data science. Vol. 47, Cambridge university press. Cited by: §I-A, §I-C. [31] C. Yu, A. Velu, E. Vinitsky, J. Gao, Y. Wang, A. Bayen, and Y. Wu (2022) The surprising effectiveness of ppo in cooperative multi-agent games. Advances in neural information processing systems 35, p. 24611–24624. Cited by: §I-A. [32] K. Zhang, Z. Yang, and T. Başar (2021) Multi-agent reinforcement learning: a selective overview of theories and algorithms. Handbook of reinforcement learning and control, p. 321–384. Cited by: §I-A, §I. [33] K. Zhang, Z. Yang, H. Liu, T. Zhang, and T. Basar (2018) Fully decentralized multi-agent reinforcement learning with networked agents. In International conference on machine learning, p. 5872–5881. Cited by: §I-A, §I-A, §VII-A. [34] Y. Zhang, G. Qu, P. Xu, Y. Lin, Z. Chen, and A. Wierman (2023) Global convergence of localized policy iteration in networked multi-agent reinforcement learning. Proceedings of the ACM on Measurement and Analysis of Computing Systems 7 (1), p. 1–51. Cited by: §I-A.