Taylor Representations for Model-Free RL in Networked MDPs

Salah Chikhi; Abdelhaq Chaoui; Asuman Ozdaglar; Saurabh Amin

stat.MLOct 4, 2026

Taylor Representations for Model-Free RL in Networked MDPs

Authors: Salah Chikhi, Abdelhaq Chaoui, Asuman Ozdaglar, Saurabh Amin

Organizations: Massachusetts Institute of Technology

Abstract

In Networked Markov Decision Processes, transition dynamics are often unknown and the state--action space grows rapidly with the number of agents. In this setting, Taylor representations naturally approximate $Q$ -functions, but a naive order- $n$ expansion over $N$ agents requires $Θ(N^n)$ coefficients. We justify these expansions under smooth expected future local rewards with controlled derivatives. Under this condition, finite-speed information propagation and discounting imply that local-critic Taylor coefficients decay exponentially with the graph distance to the farthest agent involved. Discarding distant-agent coefficients and marginalizing then yield scalable local Taylor representations with a bound controlled by graph locality. Building on these representations, we propose a scalable model-free actor--critic algorithm, establishing finite-sample critic and near-stationarity guarantees for a linear LSTD critic. We then introduce a more expressive neural TD parameterization. Unlike prior constructive spectral methods, our approach covers settings without access to a known local dynamics map, such as hidden switched linear--quadratic regulation. Across three control benchmarks, our method matches or outperforms spectral baselines while scaling efficiently to large graphs.

Figures & tables

	Qu et al.	Olsson et al.	Ren et al.	Wang et al.	Maran et al.	Ours
Networked MDP	$\checkmark$	$\checkmark^{\ddagger}$	$\checkmark$	$\checkmark$	–	$\checkmark$
Continuous state–action	–	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$
Critic representation	Tabular	Local quadratic	Spectral	Spectral	Taylor	Local Taylor
Scalable representation	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$	–	$\checkmark$
Model-free construction	$\checkmark$	$\checkmark$	– †	–	$\checkmark$	$\checkmark$
End-to-end guarantee	Stationarity	–	Stationarity	Stationarity	No-regret	Stationarity

Table 1: Comparison with representative prior representation-based approaches.

Figure 1: Critic estimation quality. Normalized critic MSE across Taylor orders and locality settings on LQR, switched LQR and the Kuramoto oscillator.

Figure 2: Policy convergence . Method comparison LQR and switched LQR (relative optimality gap), and policy convergence on Kuramoto (undiscounted return).

Figure 3: Scalability. Left: runtime per epoch on an H200 GPU as a function of the number of agents

N

. Right: relative optimality gap as a function of

N

on LQR and switched LQR.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

LQR and switched LQR
$(\kappa,\kappa_{\pi})$	$(1,1)$	$(2,1)$	$(2,2)$	$(3,2)$	$(2,3)$
LTC, $n=1/2/3$	28/70/140	66/231/616	66/231/616	120/540/1,800	66/231/616
NTC, $n=1$	4,932	5,318	5,318	5,704	5,318
NTC, $n=2$	5,322	6,293	6,293	7,524	6,293
NTC, $n=3$	5,972	8,568	8,568	12,984	8,568
MLP	17,153	17,409	17,409	17,665	17,409

Appendix

Table 2: Learned parameters of each critic in the policy experiments of Figure 2 , per agent unless marked as total (

N=50

on LQR and switched LQR,

N=40

on Kuramoto). LTC counts its coefficients, RF, RF-SAC and CDCPG their linear weights, and the other critics their network weights. The GNNs share their weights across agents and are reported as totals; twin critics count both copies.

$(\kappa,\kappa_{\pi})$	$(1,1)$	$(2,1)$	$(2,2)$ , $(3,2)$	$(2,3)$
LTC $n=1$	$(0.50,40)$	$(0.35,40)$	$(0.50,100)$	$(0.50,100)$
LTC $n=2$	$(0.35,25)$	$(0.35,25)$	$(0.50,40)$	$(0.50,40)$
LTC $n=3$	$(0.35,25)$	$(0.35,40)$	$(0.50,40)$	$(0.50,40)$
NTC $n=1$	$(0.50,400)$	$(0.50,400)$	$(0.50,2000)$	$(0.50,2000)$
NTC $n=2$	$(0.35,40)$	$(0.35,25)$	$(0.50,40)$	$(0.50,40)$
NTC $n=3$	$(0.35,40)$	$(0.35,25)$	$(0.50,25)$	$(0.50,25)$

Appendix

Table 3: Selected

(\eta,K)

on LQR.

$(\kappa,\kappa_{\pi})$	$(1,1)$	$(2,1)$	$(2,2)$ , $(3,2)$	$(2,3)$
LTC $n=1$	$(0.35,40)$	$(0.35,40)$	$(0.50,40)$	$(0.50,40)$
LTC $n=2$	$(0.50,25)$	$(0.50,25)$	$(0.50,25)$	$(0.50,25)$
LTC $n=3$	$(0.50,25)$	$(0.50,25)$	$(0.50,25)$	$(0.50,25)$
NTC $n=1$	$(0.35,40)$	$(0.35,40)$	$(0.50,40)$	$(0.50,40)$
NTC $n=2$	$(0.50,40)$	$(0.50,40)$	$(0.50,25)$	$(0.50,40)$
NTC $n=3$	$(0.50,40)$	$(0.50,40)$	$(0.50,40)$	$(0.50,40)$

Appendix

Table 4: Selected

(\eta,K)

on switched LQR.

$(\kappa,\kappa_{\pi})$	$(1,1)$	$(2,1)$	$(2,2)$	$(3,2)$	$(2,3)$
LTC $n$	$1$	$2$	$2$	$2$	$2$
LTC $(\eta,K)$	$(0.25,16)$	$(0.25,16)$	$(0.50,4)$	$(0.50,16)$	$(0.50,16)$
LTC $\lambda$	$10^{-3}$	$10^{-1}$	$10^{-3}$	$10^{-1}$	$10^{-1}$
NTC $n$	$1$	$1$	$2$	$2$	$2$
NTC $(\eta,K)$	$(0.25,16)$	$(0.25,16)$	$(0.50,16)$	$(0.50,16)$	$(0.50,16)$
MLP $\eta$	$0.25$	$0.25$	$0.25$	$0.50$	$0.50$

Appendix

Table 5: Selected hyperparameters on Kuramoto, at the Taylor order

n

shown in each panel of Figure 2 ;

\lambda

is the LSTD ridge of LTC.

Figure 4: Empirical exponential decay of action-value derivatives. For each derivative order

p=|\beta|

, we plot

H_{p}(d)/H_{p}(0)

against the graph reach

d_{i}(\beta)

. Solid curves show measured derivative magnitudes and dashed curves show the explicit theoretical rate

\rho^{d}

, with

\rho=\gamma^{1/(1+\kappa_{\pi})}

; colors indicate the policy locality radius

\kappa_{\pi}

. LQR and switched LQR derivatives are computed exactly from their quadratic and quadratic conditioned on

\sigma

value functions, so their third-order derivatives vanish. For Kuramoto (

N=20

), every derivative up to order three is maximized over states and actions: all multi-indices are enumerated at

256

visited states, and the

4

best starts per graph reach are refined by projected signed-gradient ascent (step

0.05

, fixed budget, no tolerance), giving lower bounds on the suprema. Reported

\widehat{\rho}

values are least-squares fits of

\log H_{p}(d)

over reaches above the numerical precision threshold.

Figure 5: Centroid and local-approximation ablations. (a) held-out critic fit versus the number of centroids

K

on Kuramoto (

N=6

, with encoding

s_{i}=\theta_{i}

), measured by

R^{2}=1-\sum_{s,i}\bigl(\tilde{V_{i}}(s)-V^{\mathrm{MC}}_{i}(s)\bigr)^{2}/\sum_{s,i}\bigl(V^{\mathrm{MC}}_{i}(s)-\bar{V}^{\mathrm{MC}}\bigr)^{2}

over

4096

held-out states, where

V^{\mathrm{MC}}_{i}(s)

averages the discounted return of agent

i

over

20

Monte Carlo continuations of

500

steps from

s

. (b) Mean squared error of the critic on the exact agent-mean value

\bar{V}=\frac{1}{N}\sum_{i}V_{i}

on LQR (

N=40

), as a function of the distance of the evaluated state to its assigned centroid, for LTC and NTC with

n=1,2,3

Figure 6: Taylor order ablation. Convergence of LTC for

n\in\{1,2,3\}

for different configurations

(\kappa,\kappa_{\pi})

on LQR and switched LQR.

Figure 7: Representative trajectories. Trajectories of the learned policies on networked LQR, hidden-mode switched LQR, and the Kuramoto oscillator.

Figure 8: Operating regimes in hidden switched LQR. PCA projection of state trajectories, colored by latent mode $\sigma_{t}$ for visualization; crosses denote the $K=5$ Taylor Centroid medians. Mode separation, the fraction of the variance of the two principal-component scores $z_{t}$ explained by the latent mode, $\sum_{m}n_{m}\|\bar{z}_{m}-\bar{z}\|^{2}/\sum_{t}\|z_{t}-\bar{z}\|^{2}$ (with $\bar{z}_{m}$ the mean of the $n_{m}$ points with $\sigma_{t}=m$ and $\bar{z}$ the overall mean; $0$ when all modes share the same mean, $1$ when each mode collapses to a point), increases from $0.35$ without control (left) to $0.62$ after training with $\sigma_{t}$ unobserved (right), as trajectories form clearer recurrent regions and the centroids align with the latent regimes.

Figure 9: Empirical stress test of expected reward regularity. $|\partial_{s}^{\beta}g_{i,t}^{\pi}(z,s,a)|$ versus horizon $t$ for $|\beta|\in\{1,2,3\}$ on LQR and switched LQR ( $N=50$ , learned policies with $\kappa_{\pi}=2$ ) and Kuramoto ( $N=40$ , greedy controller), at $16$ visited anchors $(z,s,a)$ and $5$ agents per environment, with $256$ rollouts per expectation. Colors: graph reach $d_{i}(\beta)=\max_{j\in\operatorname{supp}_{G}(\beta)}d_{G}(i,j)$ ; marks in the bottom strip: numerically zero derivatives; gray: finite-difference resolution range.

Explore similar work

Scalable Policy Optimization for Networked Multi-Agent Reinforcement Learning with Continuous State-Action Spaces
Jul 20, 2026Dongming Wang, Pengcheng Dai, Wenwu Yu +1Multi-Agent Reinforcement Learning Frictive Policy Optimization
Department of Electrical and Computer Engineering, University of California, Riverside, CA 92521, USA · Engineering Systems and Design Pillar, Singapore University of Technology and Design, Singapore 487372 · Frontiers Science Center for Mobile Information Communication and Security, School of Mathematics, Southeast University, Nanjing 211102, China +1
Representation Learning Enables Scalable Multitask Deep Reinforcement Learning
Jun 4, 2026Johan Obando-Ceron, Lu Li, Scott Fujimoto +3Multi-Turn Reinforcement Learning Model-Based Reinforcement Learning
Mila – Québec AI Institute · Université de Montréal · McGill University +2
Collaborative Yet Personalized Policy Training: Single-Timescale Federated Actor-Critic
May 14, 2026Leo Muxing Wang, Pengkun Yang, Lili SuSoft Actor-Critic Multi-Agent Reinforcement Learning
Northeastern University · Tsinghua University

Jul 20, 2026, cs.MAJ/K move · Enter open · S save

Scalable Policy Optimization for Networked Multi-Agent Reinforcement Learning with Continuous State-Action Spaces

Dongming Wang, Pengcheng Dai, Wenwu Yu, Wei Ren

Department of Electrical and Computer Engineering, University of California, Riverside, CA 92521, USA · Engineering Systems and Design Pillar, Singapore University of Technology and Design, Singapore 487372 · Frontiers Science Center for Mobile Information Communication and Security, School of Mathematics, Southeast University, Nanjing 211102, China+1

Multi-Agent Reinforcement Learning Frictive Policy Optimization Markov Decision Processes Optical Networks

Open paper AskPDF arXiv

Learning local policies for continuous networked systems requires accounting for the effects of decisions beyond each agent's observation neighborhood. Spatial decay limits these effects, but a finite critic must also control representation and estimation errors throughout policy optimization. We analyze the Continuous Distributed Coupled Policy Gradient (CDCPG) algorithm using local random Fourier features and least-squares temporal-difference critics. For features that retain the boundary inputs required by the local dynamics, we derive an action-value representation with separate spatial and finite-feature residuals. A global integrated transition-approximation bound and a projected Bellman argument control population prediction error without an inverse-conditioning multiplier. We then quantify the dependence of critic estimation on feature excitation and dimension, and construct simultaneous lower confidence bounds for temporal-difference conditioning along the executed iterates. Combining critic error with localized reward aggregation bounds the expected squared projected-gradient mapping by an optimization term and an explicit residual separating spatial approximation, finite features, and omitted distant rewards. For fixed neighborhoods and feature dimension, the shared-oracle sample count is inverse-squared in the excess squared-stationarity accuracy, up to logarithmic factors. The guarantee assumes known local dynamics and rewards, independent discounted-occupancy samples, and stated excitation, decay, and smoothness conditions, and is conditional on favorable feature draws. Numerical studies illustrate related implementations on a linear-coupled-quadratic benchmark.

Abstract

Explore similar work

Scalable Policy Optimization for Networked Multi-Agent Reinforcement Learning with Continuous State-Action Spaces

Representation Learning Enables Scalable Multitask Deep Reinforcement Learning

Collaborative Yet Personalized Policy Training: Single-Timescale Federated Actor-Critic