acceptodds
Under review as a conference paper at ICLR 2027

Taylor Representations for Model-Free RL in Networked MDPs

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 -functions, but a naive order- expansion over agents requires 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.

Primary area:
reinforcement learning
Keywords:
Networked Markov Decision Processes, Multi-Agent Reinforcement Learning, Model-Free Reinforcement Learning, Taylor Representation, Actor-Critic Methods

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_qEjXOpenReview ↗
Rating
2
Confidence
1
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

Overall, I think this is an interesting paper with a nice theoretical insight. The idea of extending spatial locality to higher-order Taylor derivatives is novel, and the proposed methods are well motivated and supported by solid experiments. My main concerns are about the probability guarantee in Theorem 2, the mismatch between the theory and experiments, and some limitations in the scalability and decentralization claims. I would be open to raising my score if the authors can address these concerns in the rebuttal.

Critical strengths
  1. The paper shows that not only the Q-functions but also their higher-order Taylor derivatives exhibit exponential spatial decay. This provides a nice way to reduce the representation complexity from global to local neighborhoods.
  2. The paper builds on the locality result to propose the Taylor Centroid critic, LTC, and NTC, with clear approximation–estimation tradeoffs.
  3. The authors test different environments, include several useful ablations, and scale up to 1,000 agents. The derivative-decay experiments are also helpful in supporting the theoretical motivation.
Critical weaknesses
  1. Theorem 2 has a nontrivial conditioning issue in its high-probability guarantee. The theorem claims that the critic error bound holds with probability at least 1−δ1-\delta, conditioned on the empirical LSTD matrices being well-conditioned. However, the proof first establishes an unconditional concentration bound and then intersects it with the random event C={σmin⁡(A^i)≥cLSTD}C=\{\sigma_{\min}(\widehat A_i)\ge c_{\rm LSTD}\}, which depends on the same rollout data. This seems to establish only Pr⁡(Bc∩C)≤δ\Pr(B^c\cap C)\le\delta, rather than the claimed Pr⁡(Bc∣C)≤δ\Pr(B^c\mid C)\le\delta. Without a lower bound on Pr⁡(C)\Pr(C) or a concentration argument valid after conditioning on CC, the stated confidence level does not follow. The theorem may therefore need to be reformulated or supported by an additional argument.

  2. The analysis assumes compact state/action spaces, bounded rewards, and bounded policy scores, while the LQR and switched-LQR experiments use Gaussian noise, quadratic rewards, and Gaussian policies. These violate the boundedness assumptions, so it is unclear whether Theorem 3 applies to these main benchmarks.

  3. The representation complexity can still grow quickly with the Taylor order, locality radius, state dimension, and graph degree. Also, centroid selection k(s)k(s) relies on the global state, so the critic is not fully decentralized. The stronger-performing NTC also lacks the finite-sample guarantee provided for LTC.

Questions for authors
  1. Could the authors clarify the probability statement in Theorem 2? The current proof seems to support a joint bound rather than a conditional one. Can the theorem be revised, or can the authors bound the probability of the LSTD matrices being well-conditioned?
  2. How should we understand the theoretical guarantees in the LQR and switched-LQR experiments, given the unbounded noise, rewards, and policy scores? Could the authors provide an extension of the theory or experiments under bounded settings?
  3. How important is access to the global state for centroid selection? It would be interesting to see whether the method still works well when each agent selects its centroid using only local observations.
7 comments
AuthorsOpenReview ↗

Clarifications on Theoretical Assumptions, Global Centroid Selection, and Scalability [1/2]

We thank the reviewer for the detailed and constructive feedback. We address each point below.

Q/C1. Conditional high-probability statement in Theorem 2.

The phrase "Conditionally on the centroids and on ⋂i=1Nσmin⁡(A^i)≥cLSTD>0\bigcap_{i=1}^N\\{\sigma_{\min}(\widehat A_i)\ge c_{\rm LSTD}>0\\}" incorrectly suggests a conditional probability guarantee, which is not established by our proof. Our intended statement is that, with probability at least 1−δ1-\delta, the error bound holds whenever the LSTD matrices satisfy the conditioning requirement.

More precisely, let C=⋂i=1Nσmin⁡(A^i)≥cLSTD>0C=\bigcap_{i=1}^N\\{\sigma_{\min}(\widehat A_i)\ge c_{\rm LSTD}>0\\} and let EE denote the event that the error bounds of Theorem 2 hold for all agents.

Our proof indeed establishes P(C∩Ec)≤δ\mathbb{P}(C \cap E^c) \leq \delta, that is P(Cc∪E)=1−P(C∩Ec)≥1−δ.\mathbb{P}(C^c \cup E)= 1-\mathbb{P}(C\cap E^c) \geq 1-\delta.

Thus, the correct statement is: with probability at least 1−δ1-\delta, if the empirical LSTD matrices satisfy the conditioning requirement, then the error bounds of Theorem 2 hold for all agents.

Revision. We will correct the statement of Theorem 2 in Section 3.2 and clarify its interpretation in Appendix F.

Q/C 2. Theory assumes bounded quantities, whereas LQR experiments use Gaussian noise and quadratic costs.

We agree that the theoretical Gaussian LQR does not strictly satisfy our boundedness assumptions. This discrepancy between bounded theoretical assumptions and Gaussian linear-quadratic benchmarks is common in networked RL. For instance, Ren et al. (2025) establish guarantees under compactness assumptions while evaluating a similar Gaussian LQR benchmark. Similarly, Wang et al. (2026) evaluate a Gaussian LQR benchmark with empirical state and action clipping. As acknowledged in the introductory remark of Appendix B, our experiments should be interpreted through a sufficiently large compactification of the dynamics. We elaborate on this argument below.

Interpretation of our LQR experiments. For both of our LQR settings, over any fixed finite horizon and under fixed affine Gaussian policies, the Gaussian tails of the state distributions ensure that the probability of exiting a compact state-space region of radius RR decays exponentially with R2R^2. Thus, sufficiently large clipping radii can be chosen a priori so that clipping remains inactive with arbitrarily high probability over any fixed finite collection of rollouts.

More precisely, our recorded experimental trajectories should be understood exactly as trajectories of the compactified LQR dynamics

St+1=clip⁡(ASt+BAt+εt,−R⋆,R⋆).S_{t+1}=\operatorname{clip}\left(AS_t+BA_t+\varepsilon_t,-R^\star,R^\star\right).

where clipping remained inactive. Indeed, there exists a sufficiently large fixed radius R⋆R^\star encompassing every state visited throughout our experiments and generally making clipping statistically negligible. Introducing state clipping at this radius leaves every recorded trajectory unchanged. Although state clipping was not explicitly implemented, our experimental results should be interpreted as trajectories of this compactified MDP. The same reasoning applies to switched LQR.

Actions were clipped at a very large radius in our implementation, although clipping never activated in our experimental rollouts. Consequently, the Gaussian policy scores used in our implementation coincide with the exact scores of the clipped policies on the recorded samples. Assuming bounded policy parameters during training, the clipped policies have uniformly bounded scores over the compact state-action space.

Applicability of our assumptions. Importantly, the compactified MDP has compact state and action spaces, and bounded rewards since the reward functions are smooth on these compacts.

It also satisfies Assumption 1. More specifically, although clipping introduces boundary atoms in the transition distribution, the smoothing argument of Appendix E.4.1 can be adapted by expressing expected future rewards as integrals against the Gaussian density before clipping. Differentiating this density yields derivative bounds uniform in time, policy, and network size under the bounded-degree and uniform local-regularity conditions. Hence, Assumption 1 holds for the compactified MDP. This establishes the applicability of our theoretical framework to the compactified MDP.

Furthermore, the compactified system accurately approximates the original Gaussian LQR over any fixed finite horizon, in terms of trajectory agreement and expected values on bounded evaluation regions. In particular, Gaussian tail and moment bounds imply that the corresponding finite-horizon value functions are uniformly close on any fixed bounded evaluation region. Since the LQR value function is quadratic, this supports its use as a reference in our comparisons.

Revision. We will expand the existing remark in Appendix B to clarify the compactified interpretation and Gaussian-tail argument, document action clipping in Appendix C.2.

AuthorsOpenReview ↗

Clarifications on Theoretical Assumptions, Global Centroid Selection, and Scalability [2/2]

Q/C3. On the importance of the global state for centroid selection

As explained in Section 3.1, our method does not claim fully decentralized critic evaluation: selecting centroids in the global state space is a deliberate choice that allows the cluster index to inject global information into otherwise local critics.

Global selection is particularly useful under latent system-wide conditions. Figure 8 shows that centroids align with switched LQR operating regimes. In switched LQR, multinomial logistic regression on local neighborhoods predicts the mode ZtZ_t with only 51-57% accuracy (similarly with an MLP), versus 82-84% using the global cluster index alone (assigning each cluster its majority mode), close to the 83--85% obtained by logistic regression on the full global state. These results show that global clusters capture substantial information about the latent mode. We also directly compare global versus local centroid selection (K-medians is applied for each agent's neighborhoods) on switched LQR (relative optimality gap in %, mean ± std. over five seeds):

(κ,κπ)(\kappa,\kappa_\pi)LTC globalLTC localNTC globalNTC local
(1,1)(1,1)4.73 ± .065.24 ± .064.90 ± .085.28 ± .11
(2,1)(2,1)4.68 ± .025.20 ± .044.67 ± .045.19 ± .07
(2,2)(2,2)3.44 ± .024.54 ± .063.40 ± .063.92 ± .13
(3,2)(3,2)3.45 ± .015.57 ± .063.44 ± .073.94 ± .14
(2,3)(2,3)1.63 ± .022.36 ± .051.69 ± .132.23 ± .21

Global selection yields lower gaps in all ten comparisons: by 0.51-2.12 percentage points for LTC and 0.38-0.54 for NTC (five configurations each). On LQR and Kuramoto, which lack latent global modes, local and global clustering perform similarly. This supports using global centroids to capture hidden system-wide regimes.

Revision. We will clarify global versus local centroid selection in Section 3.1, report the mode-prediction and local-clustering ablations in Appendix D.5, and discuss limitations in Section 7.

C4. Scalability of the representation complexity.

We agree that representation complexity can increase with the Taylor order, locality radius, local state dimension, and graph degree. While the dependencies highlighted by the reviewer remain, they involve local quantities that are often manageable in practice, unlike the global system dimension, which grows with NN and whose dependence our approach eliminates. In particular:

  1. Graph degree and state dimension. With other quantities fixed, pip_i scales polynomially with degree Δ\Delta and local state dimension dsd_s, which are typically small and independent of NN. Examples include building control (Δ=2\Delta=2, ds=1d_s=1) and Kuramoto (Δ=2\Delta=2, ds=2d_s=2) in Ren et al. (2025), wireless grids (Δ=8\Delta=8, ds=2d_s=2) in Qu et al. (2022), epidemic spreading (Δ=2\Delta=2, ds=2d_s=2) in Zhang et al. (2023), and building grids (Δ=4\Delta=4, ds=2d_s=2) in Shin et al. (2023). Thus, replacing dependence on NN with dependence on the typically small Δ\Delta and dsd_s yields a substantial scalability gain.

  2. Locality radius κ\kappa. Our theory establishes that the error from discarding distant agents decays exponentially with κ\kappa at a rate governed by ρ\rho, enabling accurate local approximations with small radii. Appendix D.1 further shows particularly small empirical decay rates in our environments, where κ≤3\kappa\leq 3 achieves competitive performance, although the required radius remains environment-dependent.

  3. Taylor order nn. We primarily use low orders (n≤3n\leq 3), which suffice in our experiments. For LQR and switched LQR, increasing nn from 11 to 22 substantially improves critic estimation and policy performance, while n=3n=3 brings little additional benefit (Figures 1 and 6). Similarly, low orders achieve strong performance on Kuramoto.

Hence, our claim is that, despite these dependencies, many control problems can be modeled by low-degree graphs, with small local state dimensions, and can be accurately approximated using relatively small κ\kappa and low nn. Consequently, representation complexity typically remains manageable in practice. We acknowledge that settings requiring substantially larger values of these quantities remain an interesting direction for future work.

Revision. We will clarify the dependence on κ\kappa, nn, Δ\Delta, and dsd_s and their typical values in Section 3.1 and Appendix F.6, and discuss limitations in Section 7.

C5. Guarantees and NTC.

We agree that the lack of finite-sample guarantees for NTC is a limitation, as acknowledged in Section 7. Extending such guarantees to nonlinear TD remains challenging future work. Nevertheless, NTC offers greater expressivity than LTC, and Theorem 3 still applies provided its critic approximation error is controlled.

Revision. We will clarify these distinctions in Sections 3.2 and 4.

AuthorsOpenReview ↗

References

Ren et al. (2025). Scalable Spectral Representations for Multiagent Reinforcement Learning in Network MDPs. AISTATS 2025.

Wang et al. (2026). Scalable Policy Optimization for Networked Multi-Agent Reinforcement Learning with Continuous State-Action Spaces. arXiv preprint.

Qu et al. (2022). Scalable Reinforcement Learning for Multiagent Networked Systems. Operations Research.

Zhang et al. (2023). Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learning. Proceedings of the ACM on Measurement and Analysis of Computing Systems.

Shin et al. (2023). Near-Optimal Distributed Linear-Quadratic Regulator for Networked Systems. SIAM Journal on Control and Optimization.

Reviewer_ZS8uOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper uses graph locality to construct scalable Taylor representations of local critics in continuous networked MDPs, which is a common framework in modeling multi-agent systems. The authors first prove an important Lemma 1, which suggests that in the taylor expression of the Q-function, the Taylor coefficients are decaying in the distant node. This Lemma leads to an important simplification to utilize graph locality for evaluating Q-function. The results in the lemma provides a local taylor representation for the Q-function, which is theoretically guaranteed with an error bound, and can be used for practical algorithm design. The authors design Linear / Neural Taylor Centroid which successfully mitigates the problem of dimensionality problem in Taylor representation. Empirical results validate the usefulness of the algorithm.

Critical strengths

I believe this paper is valuable and well-written for the following reasons:

  • The motivation is clear - simplifying the coefficients of Taylor representation in networked MDP is an important question.

  • The whole writting is coherent and clear. With the Lemma, take-home message, theoretical results followed by algorithms design and empirical validation. This makes the paper easy-to-follow and the logic clear.

  • The theoretical results are solid.

Critical weaknesses

I only have one concern (and this concern can be lead by my misunderstanding)

  • The ideal Taylor representation and the implemented LTC class have materially different approximation properties. With the stated feature map, LTC is affine in actions for any fixed state. A standard LQR action-value function generally contains quadratic action terms. Consequently, increasing the state Taylor order to two does not make the implemented LTC class an exact representation of quadratic QQ-functions. The misspecification term formally accommodates this issue, so it is not a contradiction of the theorem. However, the paper does not establish that this term is small for the chosen features. Claims based on quadratic structure should distinguish the ideal representation, the implemented QQ-critic, and the evaluated state-value function.
Questions for authors
  • I would thank the authors if they can clarify my concern in the weakness part.
  • In terms of empirical results, Do the gains persist when MLP and GNN baselines receive the same global centroid information?
  • How large is the irreducible hidden-mode prediction error, and can the guarantees be expressed using observable beliefs or distributional error?
4 comments
AuthorsOpenReview ↗

Clarifications on LTC Expressivity, Centroid-Augmented Baselines, and Hidden-Mode Uncertainty [1/2]

We thank the reviewer for the positive evaluation of our approach and for the constructive remarks.

Q/C1. On the approximation properties of LTC

We first clarify the role of ψi\psi_i. The canonical choice ψi(k,yi,aNiκ)=[1;μk,Niκ;aNiκ;yi]\psi_i(k,y_i,a_{\mathcal N_i^\kappa}) = [1;\mu_{k,\mathcal N_i^\kappa};a_{\mathcal N_i^\kappa};y_i] yields an LTC parameterization that is affine in local actions for fixed states. However, as noted in Footnote 2 of Section 3.2, ψi\psi_i can be adapted to better approximate QπQ^\pi. For instance, adding vec⁡(aNiκaNiκ⊤)\operatorname{vec}(a_{\mathcal N_i^\kappa}a_{\mathcal N_i^\kappa}^{\top}) to the canonical features captures quadratic action terms which may improve fitting to the quadratic QπQ^\pi of LQR, while further features can increase expressivity.

Throughout, we distinguish the true QQ-function QiπQ_i^\pi, its ideal localized Taylor representation Q^iπ\widehat Q_i^\pi, and the LTC parameterization defined through ψi\psi_i, Q~iLTC\widetilde{Q}_i^{\mathrm{LTC}}.

As the reviewer notes, the true QQ-function is quadratic in (s,a)(s,a) for LQR (it is also quadratic conditionally on the current mode for switched LQR) whereas the implemented LTC, with the canonical ψi\psi_i, remains affine in aNiκa_{\mathcal N_i^\kappa}. For fixed actions and centroid, increasing the state Taylor order from n=1n=1 to n=2n=2 introduces quadratic terms in sNiκs_{\mathcal N_i^\kappa}, improving expressivity in the state variables without capturing quadratic action dependence or guaranteeing exact representation of QπQ^\pi.

Our claim instead concerns the approximation of the state-value function. Under our affine-mean Gaussian policies, this function is quadratic in the state for LQR, and quadratic conditional on the mode for switched LQR. As stated in Section 6 and Appendix C.1, Figure 1 evaluates the approximation error of these value functions. The substantial improvement from n=1n=1 to n=2n=2, followed by saturation at n=3n=3, is consistent with this quadratic structure as n=2n=2 introduces quadratic terms in sNiκs_{\mathcal N_i^\kappa}. We do not claim that LTC represents QπQ^\pi exactly or that its misspecification error vanishes.

Revision. We will distinguish the true critic, ideal Taylor representation, and LTC parameterization in Section 3.2, and clarify the improvements from n=1n=1 to n=2n=2 in Section 6.

Q2. Do the gains remain when the MLP and the GNN receive the same centroid information?

We reran all MLP and GNN policy-convergence experiments from Figure 2, augmenting both baselines with the same global KK-medians centroids with KK as NTC. Specifically, the MLP critic of agent ii receives [sNiκ,μk(s),Niκ][s_{N_i^\kappa},\mu_{k(s),N_i^\kappa}], while each GNN node jj receives [sj,μk(s),j][s_j,\mu_{k(s),j}]. All other inputs, training budgets and step sizes remain unchanged.

We first focus on switched LQR. Global centroid information is particularly relevant here, as the dynamics depend on an unobserved operating mode. Indeed, Figure 8 shows that global clustering identifies regions associated with these latent modes, potentially helping the baselines infer the underlying regime.

The table reports the final relative optimality gap ∣J−J⋆∣/∣J⋆∣|J-J^\star|/|J^\star| (in %), as mean ± standard deviation over five seeds. Best TC denotes the best final performance between LTC and NTC.

(κ,κπ)(\kappa,\kappa_\pi)Best TCMLPMLP + μ\muGNNGNN + μ\mu
(1,1)(1,1)4.73 ± 0.065.42 ± 0.135.28 ± 0.125.65 ± 0.115.50 ± 0.06
(2,1)(2,1)4.67 ± 0.045.14 ± 0.104.70 ± 0.055.47 ± 0.075.05 ± 0.04
(2,2)(2,2)3.40 ± 0.063.84 ± 0.023.33 ± 0.024.10 ± 0.043.59 ± 0.01
(3,2)(3,2)3.44 ± 0.073.93 ± 0.023.45 ± 0.024.22 ± 0.073.71 ± 0.07
(2,3)(2,3)1.63 ± 0.022.25 ± 0.021.84 ± 0.012.59 ± 0.072.23 ± 0.05

As expected, centroid information improves both baselines, confirming the value of global clustering for capturing latent regimes. With matched centroid inputs, GNN still trails TC across all five configurations by 0.19-0.77 percentage points. MLP nearly matches TC at (2,1)(2,1) and (3,2)(3,2), slightly outperforms it at (2,2)(2,2), but trails by 0.55 and 0.21 points at (1,1)(1,1) and (2,3)(2,3), respectively.

TC also converges faster initially when κπ=1\kappa_\pi=1: after one-eighth of training, relative gaps are 4.98% (LTC), 4.94% (NTC), and 5.67% (MLP + μ\mu) at (1,1)(1,1), versus 5.06%, 5.01%, and 5.66%, respectively, at (2,1)(2,1).

For LQR and Kuramoto, without latent global modes, centroid information has negligible impact. On LQR, the final relative gap changes by at most 0.01 percentage points across five configurations (five seeds). On Kuramoto, the average undiscounted return over the final 200 epochs (three seeds) changes by at most 0.004 for MLP and 0.012 for GNN. Neither baseline changes its ranking relative to LTC/NTC. This suggests that the clustering captures information from the latent variable.

AuthorsOpenReview ↗

Clarifications on LTC Expressivity, Centroid-Augmented Baselines, and Hidden-Mode Uncertainty [2/2]

Overall, global centroids are especially useful for capturing latent regimes, while TC retains advantages beyond this information: fewer parameters than the local MLP baselines, faster early convergence for κπ=1\kappa_\pi=1, and consistently lower final mean optimality gaps than centroid-augmented GNN across all five configurations, with differences substantial relative to seed variability. Compared with centroid-augmented MLP, TC achieves clearly better performance at (1,1)(1,1) and (2,3)(2,3), while the remaining configurations exhibit comparable performance.

Revision. We will report the centroid-augmented MLP/GNN experiments in Appendix D.5 and mention their implications in Section 6.

Q3. How large is the irreducible hidden-mode prediction error? Can guarantees use observable beliefs or distributional error?

Irreducible hidden-mode error.

In switched LQR, the closed-form mode-conditioned value functions allow us to quantify the irreducible error induced by hidden modes. Writing Y=VZtπ(St)Y=V^\pi_{Z_t}(S_t), the minimum prediction error achievable from the full observed state is

Eirr:=inf⁡Y^E[(Y−Y^(St))2]=E[Var⁡(Y∣St)].\mathcal E_{\mathrm{irr}} := \inf_{\widehat Y} \mathbb E\left[\left(Y-\widehat Y(S_t)\right)^2\right] = \mathbb E[\operatorname{Var}(Y\mid S_t)].

Although the posterior distribution of ZtZ_t given StS_t is difficult to compute reliably, this quantity can be tightly bounded. The oracle lower bound and achievable upper bound are given by

E[Var⁡Zt∼Π(Zt−1,⋅)(VZtπ(St))]≤Eirr≤E[(Y−Y^NN(St))2].\mathbb{E}\left[\operatorname{Var}_{Z_t\sim\Pi(Z_{t-1},\cdot)}\left(V^{\pi}_{Z_t}(S_t)\right)\right]\leq\mathcal{E}_{\mathrm{irr}}\leq\mathbb{E}\left[\left(Y-\widehat{Y}_{\mathrm{NN}}(S_t)\right)^2\right].

The lower bound follows from the law of total conditional variance (additionally observing Zt−1Z_{t-1} can only reduce prediction error. Since ZtZ_t is conditionally independent of StS_t given Zt−1Z_{t-1}, its conditional distribution is precisely Π(Zt−1,⋅)\Pi(Z_{t-1},\cdot)). For the upper bound, we use Y^NN(St)=∑zp^(z∣St)Vzπ(St)\widehat Y_{\mathrm{NN}}(S_t)=\sum_z\widehat p(z\mid S_t)V^\pi_z(S_t), where p^\widehat p is a neural-network mode classifier trained on separate rollouts.

Using Monte Carlo evaluations, the lower and upper bounds are respectively 23.4-24.6% and 25.6-27.0% of the variance of YY across evaluated policies. Thus, approximately one quarter of the mode-conditioned value variance is irreducible even when observing the full global state. Of course, the irreducible error may be larger in other settings.

Importantly, our global clustering captures substantial latent-mode information. In fact, for switched LQR, the cluster index (labeled by each cluster's majority mode) predicts ZtZ_t with 82-84% accuracy, close to logistic regression on StS_t (83-85%) and well above prediction from local neighborhoods (51-57%). For reference, an oracle observing Zt−1Z_{t-1} achieves 89.5% by predicting no switch, the most probable outcome given Zt−1Z_{t-1} for our distribution.

Guarantees based on observable beliefs and distributional error.

Belief-based and distributional guarantees are both natural extensions of our analysis, addressing uncertainty about hidden modes and the conservativeness of uniform approximation bounds, respectively.

For belief-based guarantees, let btb_t denote the posterior distribution of the hidden mode given the observable history. Rather than conditioning the critic on the unobserved mode, one could use the belief-averaged value

Vˉπ(bt,s)=Ez∼bt[Vπ(z,s)].\bar V^\pi(b_t,s) = \mathbb E_{z\sim b_t}[V^\pi(z,s)].

This accounts for uncertainty over the current mode while incorporating information from past observations. The approximation error can then be decomposed into the error in estimating the mode-conditioned values and the error in estimating the belief distribution.

For distributional guarantees, one could replace the uniform critic-error bound used in Theorem 3 with an on-policy L2L^2 error under the state visitation distribution. We can then bound the resulting policy-gradient error in terms of the critic's L2L^2 approximation error and the second moment of the policy score. This would avoid requiring uniform accuracy over rarely visited states while preserving the general structure of our policy-gradient analysis.

Importantly, our global clustering already aims to capture latent regime information from observed states without explicitly maintaining beliefs, as supported by the results above. These extensions suggest corresponding critic-approximation and near-stationarity guarantees, although establishing finite-sample LSTD estimation bounds in these settings would require additional analysis.

Revision. We will add the irreducible-error bounds and mode-prediction results to Appendix D.5, and discuss belief-based and distributional extensions in Section 7.

I thank the authors for their rebuttal. Given that my concerns are generally addressed, I would like to maintain my positive score.

We thank the reviewer for their constructive feedback and are pleased that they have maintained their positive assessment of our work.

Reviewer_2dcjOpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper considers cooperative model-free MARL in network MDPs. Specifically, they consider using Taylor representations as a basis for the critic for the local Q functions, and show that under an assumption of smooth expected future local rewards with controlled derivatives (Assumption 1), an exponential decay type result holds and the local-critic Taylor coefficients of the local Q-function decay exponentially with kappa outside a kappa-hop neighborhood. Building on this observation, they propose two versions of their algorithm, one where the coefficient features are fixed (linear LSTD critic), and one where they are also learned (neural TD paramaterization). For the linear LSTD version, they are able to obtain finite-sample local critic approximation error bounds (up to the approximation error incurred by omitting the agents outside the kappa-hop neighborhood, the approximation error of using the fixed coefficient features, and statistical error). For the neural TD version, they do not have finite-sample bounds.

In terms of experiments, they provide results showing that their algorithm is competitive with existing baselines.

Critical strengths
  1. The idea of combining Taylor representations and exponential decay in network MARL is novel and interesting to me. Compared with existing works that typically rely on knowledge of the transition kernel, their method is able to work without knowledge of the transition kernel.
Critical weaknesses
  1. Assumption 1 is a key assumption. It would be nice to have the authors explain concisely in the main text when it holds. Currently the explanation is provided in a long writeup in the Appendix, which is not very friendly from an exposition point of view, given the central importance of this assumption.

  2. The choice of the centroids is important. For more challenging nonlinear problems, the number of clusters may need to be large perhaps even exponential in the dimension, and the strategy of sharing the same w_i weights also may not work as well.

Questions for authors
  1. Can the authors provide some intuition as to when Assumption 1 will not hold? This will provide the reader with better intuition for the nature of Assumption 1.
3 comments
AuthorsOpenReview ↗

Clarifications on Assumption 1 and Centroid Scalability

We thank the reviewer for their positive assessment and recognition of our work.

Q/C1. When does Assumption 1 fail/hold?

Sufficient conditions. We will summarize the key sufficient conditions for Assumption 1 immediately after its statement: (i) smooth dynamics with Gaussian noise; (ii) smooth finite-dimensional spectral transition representations; and (iii) MDPs satisfying sufficiently high-order Mild smoothness, as detailed in Appendix E.

Where the assumption fails. We provide two main ways Assumption 1 can fail: (i) nonsmooth expected rewards, or (ii) smooth expected rewards whose derivatives grow too quickly over time.

1. Non-smooth expected rewards. Assumption 1 fails when expected future rewards lack sufficient smoothness. This can occur when the transition dynamics are non-smooth and the rewards capture this lack of smoothness. Consider the following deterministic single-agent MDP: st+1=max⁡(0,st),r1(s)=s,s∈[−1,1].s_{t+1}=\max(0,s_t),\qquad r_1(s)=s,\qquad s\in[-1,1]. For every t≥1t\geq 1, the expected reward satisfies Eπ[r1(St)∣S0=s,A0=a]=max⁡(0,s),\mathbb E_\pi[r_1(S_t)\mid S_0=s,A_0=a]=\max(0,s), which is not differentiable at s=0s=0, violating Assumption 1 for any q≥2q\geq 2. As discussed in Appendix E, stochastic noise can mitigate such nonsmoothness, while nonsmooth dynamics need not violate the assumption if their irregularities do not affect expected rewards.

2. Exploding derivatives of expected rewards. Expected rewards can be smooth while their derivatives grow exponentially with tt. Consider, for λ>1\lambda > 1, the following deterministic MDP with one agent:

st∈[−1,1],st+1=f(st)=tanh⁡(λst),r1(s)=s.s_t\in[-1,1],\qquad s_{t+1}=f(s_t) = \tanh(\lambda s_t),\qquad r_1(s)=s.

Similarly, for t≥0t \geq 0, we have

g1,t(s):=Eπ[r1(St)∣S0=s,;A0=a]=f∘t(s).g_{1,t}(s) := \mathbb{E}_{\pi}\left[ r_1(S_{t}) \mid S_0=s,\\; A_0=a\right] = f^{\circ t}(s).

One can show that g1,t′(0)=λtg_{1,t}'(0)=\lambda^t. Thus, in particular, sup⁡t≥0∣g1,t∣Csq=+∞\sup_{t \geq 0}\\|g_{1,t}\\|_{C^q_s}=+\infty for all q≥2q\geq 2, violating the uniform in time derivative bound of Assumption 1.

Importantly, in Appendix E, we show that Assumption 1 can be weakened to requiring ∑t≥0γt∣gi,t∣Csq<∞\sum_{t\geq 0}\gamma^t\\|g_{i,t}\\|_{C^q_s}<\infty uniformly over agents and policies. Here, if γλ≥1\gamma\lambda\geq 1, we have

+∞=∑t≥0γt∣g1,t′(0)∣≤∑t≥0γt∣g1,t∣Csq,+\infty=\sum_{t\geq 0}\gamma^t|g_{1,t}'(0)| \leq\sum_{t\geq 0}\gamma^t\\|g_{1,t}\\|_{C^q_s},

for all q≥2q\geq 2. Hence, even this weaker condition fails when γλ≥1\gamma\lambda\geq 1. The intuition is that discounting must dominate the growth of expected-reward sensitivities over time.

Revision. We will summarize the sufficient conditions and counterexamples after Assumption 1 and add both counterexamples to Appendix E.

C2. On centroid selection and shared coefficient weights.

We agree that K-medians can be challenging in high dimension, as acknowledged in Section 7. As the reviewer notes, the shared weights of LTC may lack expressivity as KK grows, as captured by εˉlin\bar{\varepsilon}_{\mathrm{lin}} and Figure 5.a. However, three aspects of our approach mitigate this limitation.

1. Role of the Taylor expansion order. With few centroids, states may lie far from Taylor expansion points. Higher-order Taylor expansions help by providing accurate approximations over larger regions, reducing the need for additional centroids. Indeed, Figure 5a shows that, on Kuramoto, higher Taylor orders allow LTC to achieve its best critic fit with fewer clusters. Consistently, Figure 5b shows that increasing the Taylor order substantially reduces critic error, particularly at larger distances from centroids. Hence, increasing nn can be a substitute when increasing KK is costly.

2. Exploiting the structure of visited states. Rather than covering the entire ambient state space, we focus on recurrent regions which may require a smaller K. Trajectories may concentrate around a few operating regimes. In our 50-agent (50-dimensional) switched LQR, just K=5K=5 centroids capture recurrent regions associated with the five unobserved modes (Figure 8). We also successfully scale LQR and switched LQR to 1000 agents (1000 dimensional state) without large KK. Hence, depending on the problem, the required number of centroids may stay manageable as the dimension grows.

3. Shared coefficient weights and the role of NTC. Figure 5a shows that LTC's performance eventually deteriorates with increasing KK. In contrast, NTC retains shared weights with a more expressive neural map and continues improving up to K=2048K=2048, without such deterioration. These results suggest that NTC can better accommodate large numbers of centroids when LTC's shared coefficients become restrictive.

Nevertheless, we agree that high-dimensional problems without particular structure in the visited states may require many centroids and remain challenging.

Revision. We will clarify the tradeoff between KK, Taylor order, and coefficient expressivity in Section 3.2 and Appendix D.2.

Reviewer_2dcjOpenReview ↗

Thanks for the responses

I thank the authors for addressing my concerns. I have thus increased my score.

We thank the reviewer for their positive feedback and for increasing their score. We greatly appreciate their time and thoughtful engagement with our work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.